Fenwick Tree
hard
Mr. Pepcoder has an array A, and his Friend love to do operations on the array. The operations can be a query or an update. For each query the Friend say two indices l and r , and their father answers back with the sum of the elements from indices l to r (both included). When there is an update, the friend says an index i and a value x , and Pepcoder will add x to ith index of array (so the new value of arr[i] is arr[i] + x ). Because indexing the array from zero is too obscure for children, all indices start from 1.
Constraints
1 <= N <= 10^6 1 <= Q <= 10^5 1 <= l,r,i <= N -10^9 <= arr[i] <= 10^9
Format
Input
The first line of the input contains N. The second line contains N integers, the initial values of the array. The third line contains Q, the number of operations that will be made. Each of the next Q lines contains an operation. Query operations are of the form (q l r ) , while update operations are of the form (u i x) .
Output
You have to print the answer for every query in a different line, in the same order of the input.
Example
Sample Input
10
1 23 4 10 24 33 -1 -9 7 4
6
q 2 5
q 1 9
u 3 -2
q 4 5
u 6 10
q 4 9
Sample Output
61
92
34
74
Question Video
