Arrays and searching 0/120

Fenwick trees for prefix sums and updates · 2 of 3 Advanced

Range update, point query

Add to a whole range and read one value, by keeping a difference array in a Fenwick tree.

1,081 words · 5 min read

Part 1 of 3 Range add, point read

Add to a range and read one value

On the main page a change touched one position and a question covered a range. The next problem is the other way round: a change adds an amount to a whole range of positions, and a question asks for one value.

You get an array of nn integers x1,…,xnx_1, \dots, x_n and qq queries. A query 1 a b u adds uu to every value at positions aa through bb. A query 2 k asks for the current value at position kk.

The first line holds nn and qq, the second the nn values, and each further line one query. Print the answer to every query of the second kind.

Constraints

  • 1≤n,q≤2⋅1051 \le n, q \le 2 \cdot 10^5
  • 1≤xi,u≤1091 \le x_i, u \le 10^9
  • 1≤k≤n1 \le k \le n
  • 1≤a≤b≤n1 \le a \le b \le n

Sample · Input

8 3
3 2 4 5 1 1 5 3
2 4
1 2 5 1
2 4

Output

5
6

In the sample, position 4 starts at 5. The second query adds 1 to positions 2 through 5, so position 4 then reads 6.

Adding uu to each position of the range costs up to nn writes per query, which is 4×10104 \times 10^{10} writes at these limits. A difference array brings a range addition down to two writes, but it turns the differences back into values with one pass over the whole array, which pays off only when every addition comes before every read. Here reads and additions alternate.

Recall how a difference array records a range addition. diff starts as all zeros. With positions numbered from 1, as on the main page, adding uu to positions aa through bb makes two writes: +u+u at position aa, and −u-u at position b+1b + 1. The amount added to a position so far is then the running sum of diff up to that position. Here is the sample after its query 1 2 5 1:

The two highlighted writes are the +1+1 at position 2 and the −1-1 at position 6. Each value now is its starting value plus the running sum above it.

The running sum is 1 from position 2, where the +1+1 was written, to position 5, and 0 again from position 6, where the −1-1 cancels it. Position 4 reads its starting value plus its running sum, 5+1=65 + 1 = 6.