Redirecting to

Fenwick Tree

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.
Input Format
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 Format
You have to print the answer for every query in a different line, in the same order of the input.
Question Video
1 <= N <= 10^6
1 <= Q <= 10^5
1 <= l,r,i <= N
-10^9 <= arr[i] <= 10^9
Sample Input
1 23 4 10 24 33 -1 -9 7 4
q 2 5
q 1 9
u 3 -2
q 4 5
u 6 10
q 4 9
Sample Output

  • Asked in Companies
  • Related Topics

Video Solution

Code Solution

Id Name