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
a_{i }(so the new value of a_{i } is a_{i} + 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.
Input
The first line of the input contains N (1 ≤ N ≤ 10^{6} ) . The second line contains N integers
a_{i} (− 10^{9} ≤ a_{i} ≤ 10^{9} ) , the initial values of the array. The third line contains Q (1 ≤ Q ≤ 3 × 10^{5} ) ,
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 , − 10^{9} ≤ x ≤ 10^{9} ) .
Output
You have to print the answer for every query in a different
line, in the same order of the input.
Example
Input: 10
3 2 4 0 42 33 1 2 4 4
6
q 3 5
q 1 10
u 5 2
q 3 5
u 6 7
q 4 7 Output: 46
89
44
79
hide comments
aditya04848spo:
20210408 16:34:20
don't submit in python3 instead submit in pypy2, ac 0.67 with fast i/o in pypy2 

nadstratosfer:
20200715 19:54:08
pandey101299, that's some sixth sense insight right here. 

pandey101299:
20200715 14:00:06
easy one basic fenwick tree 

scolar_fuad:
20200410 12:14:02
this is must learn bit problem instead of lazy segment tree


aryan12:
20200405 21:22:00
Must do BIT for learners. Good problem. AC in one go (0.37 sec) 

sapjv:
20191010 15:31:58
Segment Tree  AC in 0.13 sec


aj_254:
20190912 23:26:43
solvable in pypy just use standard i/o. 

rul0:
20190122 17:20:31
Time limit too strict for Python 

Bojan Rosko:
20181005 12:41:34
Watch out for int32 overflow... 

arpit728:
20180520 17:02:56
Time limit too strict for Java 
Added by:  BerSub 
Date:  20161017 
Time limit:  0.400s1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 GOSU 