FENTREE - Fenwick Trees
Mr. Fenwick has an array a with many integers, and his children love to do operations on the
array with their father. The operations can be a query or an update.
For each query the children 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 children say an index i and a value x , and Fenwick will add x to
ai (so the new value of ai is ai + x ).
Because indexing the array from zero is too obscure for children, all indices start from 1.
Fenwick is now too busy to play games, so he needs your help with a program that plays with his
children for him, and he gave you an input/output specification.
The first line of the input contains N (1 ≤ N ≤ 106 ) . The second line contains N integers
ai (− 109 ≤ ai ≤ 109 ) , the initial values of the array. The third line contains Q (1 ≤ Q ≤ 3 × 105 ) ,
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 ” ( 1 ≤ l ≤ r ≤ N ) , while update operations are of the form
“u i x ” ( 1 ≤ i ≤ N , − 109 ≤ x ≤ 109 ) .
You have to print the answer for every query in a different
line, in the same order of the input.
3 2 4 0 42 33 -1 -2 4 4
q 3 5
q 1 10
u 5 -2
q 3 5
u 6 7
q 4 7 Output: 46
for c# take care io, use StreamReader / Writer
don't submit in python3 instead submit in pypy2, ac 0.67 with fast i/o in pypy2
pandey101299, that's some sixth sense insight right here.
easy one basic fenwick tree
this is must learn bit problem instead of lazy segment tree
Must do BIT for learners. Good problem. AC in one go (0.37 sec)
Segment Tree - AC in 0.13 sec
solvable in pypy just use standard i/o.
Time limit too strict for Python
Watch out for int32 overflow...