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.
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
ahmadf:
2024-08-24 20:56:10
Use printf and scanf instead cout and cin, otherwise it give TLE |
|
masterlemos:
2021-08-22 21:39:05
for c# take care io, use StreamReader / Writer |
|
aditya04848spo:
2021-04-08 16:34:20
don't submit in python3 instead submit in pypy2, ac 0.67 with fast i/o in pypy2 |
|
nadstratosfer:
2020-07-15 19:54:08
pandey101299, that's some sixth sense insight right here. |
|
pandey101299:
2020-07-15 14:00:06
easy one basic fenwick tree |
|
scolar_fuad:
2020-04-10 12:14:02
this is must learn bit problem instead of lazy segment tree
|
|
aryan12:
2020-04-05 21:22:00
Must do BIT for learners. Good problem. AC in one go (0.37 sec) |
|
sapjv:
2019-10-10 15:31:58
Segment Tree - AC in 0.13 sec
|
|
aj_254:
2019-09-12 23:26:43
solvable in pypy just use standard i/o. |
|
rul0:
2019-01-22 17:20:31
Time limit too strict for Python |
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 |