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 a 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.

Input

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 ) .

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
rul0: 2019-01-22 17:20:31

Time limit too strict for Python

Bojan Rosko: 2018-10-05 12:41:34

Watch out for int32 overflow...

arpit728: 2018-05-20 17:02:56

Time limit too strict for Java

vanthuan208: 2017-06-20 08:40:48

lazy segment tree!

gaurav sharma: 2017-05-19 20:24:48

good one !

Last edit: 2017-05-20 05:56:20
Jitesh: 2016-10-19 12:30:33

@spojpriya. You can't do it directly. But, you can try this ( http://spojtoolkit.com ). You might find it useful.

spojpriya: 2016-10-19 08:04:34

How can I check why I'm getting wrong answer for my solution?
As I think my code is correct .

Last edit: 2016-10-19 08:05:23
sarvagya: 2016-10-18 11:52:23

Shouldnt this be in tutorial ?


Added by:BerSub
Date:2016-10-17
Time limit:0.400s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU