Moonhay Queries

# Moonhay Queries ## Problem Statement Farmer Cow has just discovered an ancient barn filled with hay bales at each position along a long path. She wants to keep track of the total amount of hay in any contiguous section of the barn, and she also occasionally adds hay to specific positions. You are given an array of `N` hay values (initially, position `i` has `hay[i]` units of hay). You must support `Q` operations: - **Update**: Add `delta` units of hay to position `i`. - **Query**: Find the sum of hay from position `l` to position `r` (inclusive). ## Input Format - **Line 1:** Two integers `N` and `Q` (the number of positions and number of operations). - **Line 2:** `N` integers `hay[1], hay[2], ..., hay[N]` (initial hay values at each position). - **Lines 3 to Q+2:** Each line describes an operation: - `U i delta` — Add `delta` to position `i`. - `Q l r` — Query the sum from position `l` to position `r` (inclusive). ## Output Format For each query operation, print the sum of hay from position `l` to position `r` on a separate line. ## Constraints - `1 ≤ N, Q ≤ 100,000` - `1 ≤ i, l, r ≤ N` (all positions are 1-indexed) - `l ≤ r` - `0 ≤ hay[i] ≤ 10^9` - `0 ≤ delta ≤ 10^9` ## Sample Input ``` 5 5 1 2 3 4 5 Q 2 4 U 3 7 Q 1 3 Q 3 5 ``` ## Sample Output ``` 9 13 19 ``` ## Explanation Initial array: `[1, 2, 3, 4, 5]` 1. Query sum from position 2 to 4: `2 + 3 + 4 = 9` 2. Update position 3 by adding 7: array becomes `[1, 2, 10, 4, 5]` 3. Query sum from position 1 to 3: `1 + 2 + 10 = 13` 4. Query sum from position 3 to 5: `10 + 4 + 5 = 19`