Arrays and searching 0/120

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

Point updates and prefix sums

Keep range sums fast while single values change, by storing the sums of blocks whose lengths are the lowest set bits of their end positions.

4,090 words · 19 min read

Part 1 of 8 Fenwick trees

Range sums on an array that changes

A prefix array answers each range sum with one subtraction, on the condition that the array stays fixed between questions. This page drops that condition: values change, and range sums are asked for in between the changes.

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

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 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 3 1
2 1 4

Output

14
2
11

The sample's array has eight values. The problem numbers positions from 1, and so does this page:

The first query asks for positions 1 to 4, which hold 3+2+4+5=143 + 2 + 4 + 5 = 14, and the second for positions 5 and 6, which hold 1+1=21 + 1 = 2. The third sets position 3 to 1. The last query asks for positions 1 to 4 again and now gets 3+2+1+5=113 + 2 + 1 + 5 = 11.

There are two simple ways to store the array, and each makes one kind of query slow. With the plain array, a change is one write, but a sum adds up to nn values. With a prefix array, a sum is one subtraction, but a change has to rewrite every entry that includes the changed position. Here is prefix before and after position 3 changes from 4 to 1:

prefix[i] is the sum of the first i values. The highlighted entries are the ones the change rewrote.

Six of the nine entries changed, and a change at position 1 would rewrite all of them except prefix[0]. So whichever array we choose, one kind of query can cost nn steps. The problem allows 200,000 values and 200,000 queries:

200,000×200,000=4×1010 steps200{,}000 \times 200{,}000 = 4 \times 10^{10} \text{ steps}

At about 10810^8 simple steps a second in C++, that is 400 seconds of work against a one-second limit, and a loop written in Python is about ten times slower.

A Fenwick tree, also called a binary indexed tree, is a third way to store the array. It keeps the sums of certain blocks of positions, chosen so that every prefix is made of a few blocks and every position lies in only a few blocks. A prefix sum then adds a few stored numbers, and a change rewrites a few. With 200,000 values, a prefix sum reads at most 17 stored numbers and a change rewrites at most 18. The blocks nest inside one another, so they form a tree, but the whole structure is stored as one array.