Fenwick tree

A Fenwick tree, also called a binary indexed tree, keeps the sums of an array that changes: it adds a number to one element and answers "what is the sum of elements $l$ to $r$ ?" in $O (lo g n)$ O(\log n) time each. For the minimum or maximum of a changing array, use a segment tree.

Take a shop receipt of 8 lines and its prefix sums, with the 0 in front. The prices are the array: line $i$ is element $i$ .

line		1	2	3	4	5	6	7	8
price		4	2	7	1	5	3	6	2
prefix sum	0	4	6	13	14	19	22	28	30

Lines 3 to 6 cost 22 − 6 = 16. Now line 4 changes from 1 to 6 euros. The prefix sums at lines 4 to 8 all include the old 1, so all 5 of them must be rewritten. On an array of $n$ elements, one change can rewrite up to $n$ prefix sums: $O (n)$ (time complexity). Keeping only the prices makes a change one write, but then each question is $O (n)$ additions.

A Fenwick tree does both in $O (lo g n)$ O(\log n), so it is for changes and questions that come mixed. If all the changes come before all the questions, apply them to the array and build prefix sums once.

How it works

The tree is an array t of the same length as the array it describes. Each cell t[i] holds the sum of a block of elements that ends at position i. The block's length is the largest power of two that divides i, which is the value of the lowest 1 bit of i written in binary. 6 is 110 in binary, so cell 6 holds the 2 elements ending at position 6: 5 + 3 = 8. 4 is 100, so cell 4 holds elements 1 to 4, which sum to 14. Every odd cell holds one element. In Fig. 1 each cell's block is drawn as a bar under the array, ending at the cell's own position.

The array 4 2 7 1 5 3 6 2 at positions 1 to 8 with each position's binary, and under it four rows of grey bars by length 1, 2, 4 and 8: each bar covers the block of one Fenwick cell, ends at that cell's position and shows its sum: cell 1 holds 4, cell 2 holds 6, cell 3 holds 7, cell 4 holds 14, cell 5 holds 5, cell 6 holds 8, cell 7 holds 6 and cell 8 holds 30.

Fig. 1. Each cell holds the sum of the bar under it. The bar ends at the cell's own position, and its length is the lowest 1 bit of the position.

The sum of elements 1 to 7 starts with cell 7, which holds element 7. The block before it ends at position 6, so the next is cell 6 (elements 5 to 6), then cell 4 (elements 1 to 4), and then nothing is left: 6 + 8 + 14 = 28. In Fig. 2 the blue bars sit end to end, with no gap and no overlap.

The array 4 2 7 1 5 3 6 2 above four rows of Fenwick cell blocks; cells 7 (sum 6, binary 111), 6 (sum 8, binary 110) and 4 (sum 14, binary 100) are blue and sit end to end, the other cells are grey, and a bottom row spanning positions 1 to 7 shows their total 28.

Fig. 2. Going down from cell 7, the sum of elements 1 to 7 reads the blue cells 7, 6 and 4.

Going down from a cell by the length of its block drops its lowest 1 bit: 111, 110, 100, then 0. So a prefix ending at position $r$ reads one cell per 1 bit of $r$ , at most about $lo g_{2} n$ \log_2 n cells. A range sum is two prefixes, as with prefix sums: elements 3 to 6 are the sum up to 6 minus the sum up to 2.

A change to one element must reach every cell whose block contains it. Element 3 is in cells 3, 4 and 8. Going from a cell to the next one that holds the same element means climbing, that is, adding its lowest 1 bit: 3 + 1 = 4, 4 + 4 = 8, and 8 + 8 = 16 is past the end.

The array 4 2 7 1 5 3 6 2 above four rows of Fenwick blocks of lengths 1, 2, 4 and 8; the column of position 3 is outlined, and the three blocks that contain it, cell 3 (sum 7), cell 4 (elements 1 to 4, sum 14) and cell 8 (elements 1 to 8, sum 30), are red, while the other blocks are grey.

Fig. 3. Element 3 is inside the red bars 3, 4 and 8, the cells a change climbs through.

From 3, adding the lowest 1 bit gives 4, whose lowest 1 bit is larger, so block 4 reaches back past position 3. The cells 5, 6 and 7 between 4 and 8 have smaller lowest 1 bits than 4, so their blocks start after position 4 and miss element 3 (Fig. 3). From 4 the same argument gives 8, whose block starts at 1. Each step at least doubles the lowest 1 bit, so a change touches at most about $lo g_{2} n + 1$ \log_2 n + 1 cells.

Step-by-step Fenwick tree over the array 4 2 7 1 5 3 6 2: the sum of elements 3 to 6 reads cells 6, 4 and 2 and gives 22 − 6 = 16; adding 5 to element 4 changes cells 4 (14 to 19) and 8 (30 to 35); the same sum then gives 27 − 6 = 21; the sum of elements 1 to 8 reads cell 8, 35.

The array and its Fenwick cells, as in Fig. 1. The first question is the sum of elements 3 to 6: the sum up to 6 minus the sum up to 2.

1/14

Fig. 4. Step through the questions and the change with the buttons or the arrow keys. Blue cells are read by a question, red cells are changed.

The change wrote 2 cells instead of rewriting 5 prefix sums.

In C++

The standard library has no Fenwick tree. The cells are a vector<long long> t of size n + 1, with t[0] unused.

The lowest 1 bit of p is p & -p. In C++, -p is all bits of p flipped, plus 1, so the lowest 1 of p and the zeros after it come back unchanged and every higher bit is flipped. & keeps only that lowest 1: 12 is 1100, and 12 & -12 is 100, which is 4.

To build the tree, start with zeros and add each element: add(i, a[i]) for every i, $O (n lo g n)$ O(n \log n) in total.

The input is n and q, then n numbers, then q lines, each + p x (add x to element p) or ? l r (print the sum of elements l to r; l may be greater than r). The example above is this input:

8 4
4 2 7 1 5 3 6 2
? 3 6
+ 4 5
? 3 6
? 1 8

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int n;
vector<long long> t;   // cells t[1] to t[n]; t[0] is unused

// climb to the next block: add to cell p, then add its lowest 1 bit
void add(int p, long long x) {
    for (; p <= n; p += p & -p)
        t[p] += x;
}

// read a prefix: take cell r, then go down by dropping its lowest 1 bit
long long sum(int r) {
    long long s = 0;
    for (; r > 0; r -= r & -r)
        s += t[r];
    return s;
}

int main() {
    int q;
    cin >> n >> q;
    t.assign(n + 1, 0);

    // add each element
    for (int i = 1; i <= n; i++) {
        long long a;
        cin >> a;
        add(i, a);
    }

    for (int j = 0; j < q; j++) {
        char c;
        cin >> c;
        if (c == '+') {
            int p;
            long long x;
            cin >> p >> x;
            add(p, x);
        } else {
            int l, r;
            cin >> l >> r;
            if (l > r) swap(l, r);   // remove if the input guarantees l <= r
            // two prefixes
            cout << sum(r) - sum(l - 1) << '\n';
        }
    }
}

The cells are long long: with $1 0^{5}$ 10^5 elements up to $1 0^{9}$ 10^9, a sum reaches $1 0^{14}$ 10^{14}, far past int.

Setting an element

When a problem says "set element p to x", the tree can still only add. Keep the current values in a vector a and add the difference x - a[p].

Adding to a range, reading one element

Some problems add x to every element from l to r and ask for single elements. Element i is the prefix sum of the difference array up to i, so keep the tree over the difference array: then sum(i) is element i. A range add changes two differences, add(l, x) and add(r + 1, -x). On the receipt, the difference array is 4, −2, 5, −6, 4, −2, 3, −4. Adding 2 to elements 2 to 5 is add(2, 2) and add(6, -2); then sum(4) is 3, the old 1 plus 2, and sum(6) is still 3. (For r = n the second call does nothing, since n + 1 is past the end.)

A table

For a table of n rows and m columns, where one entry changes and a question asks for the sum of a rectangle, keep t of size (n + 1) × (m + 1) and nest the two loops, one over rows and one over columns. A rectangle sum comes from four prefix sums, as with prefix sums on a table, and each operation is $O (lo g n \cdot lo g m)$ O(\log n \cdot \log m).

Examples of use

How many earlier elements are smaller

Walk through the array from left to right and keep a Fenwick tree over values, with a 1 at each value seen so far. Before adding value v, sum(v - 1) counts the earlier elements smaller than v, and the number seen so far minus sum(v) counts the earlier larger ones. On 3 1 2, before adding 2 the tree holds 3 and 1, so sum(1) and sum(2) are both 1: one earlier element is smaller and 2 − 1 = 1 is larger. Adding up the larger ones over the array gives the number of inversions (pairs i < j with a[i] > a[j]) in $O (n lo g V)$ O(n \log V), where $V$ is the largest value. When values go up to $1 0^{9}$ 10^9, first replace each value by its rank among the sorted values with coordinate compression, so the tree has $n$ cells and the count takes $O (n lo g n)$ O(n \log n).

Reading all the questions first

For "how many elements of l to r are less than x?", read all the questions before answering any. Sort the elements by value and the questions by x, and keep a tree over positions. Take the questions in increasing x. Before answering one, add 1 at the position of every element smaller than its x that is not yet in the tree, then answer with sum(r) - sum(l - 1). The whole method takes $O ((n + q) lo g n)$ O((n + q) \log n) after sorting.

Common mistakes

Swapping the two directions, so that add goes down with p -= p & -p. The building calls break too, and the program prints 15, 20 and 2 on the example instead of 16, 21 and 35. add climbs with += and sum goes down with -=.
Stopping add at p < n. This also breaks the build: on the example cell 8 stays 0, and the sum of elements 1 to 8 prints 0 instead of 35. Use p <= n and give t size n + 1.

Similar structures

A segment tree also does both operations in $O (lo g n)$ O(\log n) and works for the minimum, the maximum and other operations. A Fenwick tree answers l to r as one prefix minus another, so it works for sums and XOR. The minimum can't be subtracted: on the receipt, the minimum up to 4 and the minimum up to 6 are both 1, but the minimum of elements 5 to 6 is 3, and nothing gets 3 from the two prefixes. Adding to a range and asking range sums takes two Fenwick trees or a segment tree.