2001. Range Sums While the Values Keep Changing
An array of n integers is given, numbered from 1. Then q operations arrive:
add i v add v to position i
sum l r print the total of positions l through r inclusive
Print one line for each sum.
3 1 4 1 5
sum 1 5 -> 14
add 2 10 the array becomes 3 11 4 1 5
sum 1 3 -> 18
sum 2 2 -> 11
## What most people try first
A prefix-sum array, which problem 721 already showed answers any range in one
subtraction. It is the right instinct and it dies on the first add: changing
one value invalidates every prefix from that point on, so the array has to be
rebuilt at O(n) per update. With n and q both at 2 * 10^5 that is
4 * 10^10 operations.
Scanning the range instead is O(n) per QUERY, which is the same total from
the other direction. Neither is a compromise between the two; both are the
worst case of one and the best of the other.
## A tree of partial sums
A Fenwick tree stores, at index i, the sum of the i & (-i) values ending at
i. That expression is the lowest set bit of i, so index 8 covers eight
values, index 12 covers four, and an odd index covers one.
add(i, v): while i <= n: t[i] += v; i += i & (-i)
pre(i): s = 0; while i > 0: s += t[i]; i -= i & (-i); return s
Each loop strips or adds one bit, so both run in O(log n) steps: at most 18
for n = 200000. A range is pre(r) - pre(l - 1), the same subtraction the
prefix array used.
## Why the indices must start at 1
i & (-i) is 0 when i is 0, so add would loop forever and pre would never
terminate. The structure is 1-indexed for that reason, not by convention. Read
the input however you like, but the internal array is t[1 .. n].
## Overflow
2 * 10^5 values of up to 10^9 total 2 * 10^14, far past the 2147483647
a signed 32 bit integer holds. The running total needs 64 bits. Note the
individual values do not: 10^9 fits comfortably, and so does 2 * 10^9.
## Cost
O((n + q) log n), about 7 * 10^6 steps at the limits, with O(n) memory.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `-10^9 ≤ each starting value ≤ 10^9` - `1 ≤ i ≤ n` and `-10^9 ≤ v ≤ 10^9` - `1 ≤ l ≤ r ≤ n`
Input
The first line contains two integers n and q.
The second line contains n integers, the starting values.
Each of the next q lines is either add i v or sum l r.
Output
Print one integer on its own line for every sum operation, in the order the operations arrive. An add prints nothing.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.