Fenwick Tree (Binary Indexed Tree)

A leaderboard, a bank ledger, a contest scoreboard: the numbers keep changing, and someone keeps asking for the total over a range. The Fenwick tree does both in O(log n) with about a dozen lines of code, all built on one bit trick: x & −x.

★ Lecture: tree_Fenwick · Zaza Gamezardashvili▶ video intermediate⏱ 20 min read

←Builds on

1Prefix Sums, Two Pointers & Sliding WindowPrefix sums answer a range in O(1) but must be recounted after every change; a Fenwick tree keeps both fast.2Binary Search & Search on the AnswerLike binary search, every step works with powers of two, so update and query take O(log n).

Leads to→

9Bit ManipulationThe Fenwick jumps idx += idx & -idx are the lowest set bit trick; this stage explains it in general.+Segment TreeA Fenwick tree answers prefix sums; a segment tree also answers min or max on any range [L, R], which Fenwick cannot.

1Learn 2Watch 3Play 4Check 5Practice

Learn

The idea, the mechanics and the cost.

01The problem: changes and range sums

You are given a sequence of n numbers, and two kinds of requests keep arriving (slide 2):

change the value of element i;
report the sum of the elements on an interval [x, y].

If the array never changes, prefix sums solve it: store prefix[i] = a[1] + … + a[i], and the sum on [x, y] is prefix[y] − prefix[x − 1]. In the lecture’s array of 16 numbers the sum on [6, 13] is 3+1+4+2+5+2+2+3 = 22, or, with a single subtraction, 33 − 11 = 22.

With dynamic data this breaks down: after every change of a[i], all prefix sums from i to n must be recounted, O(n) work per change. The Fenwick tree (binary indexed tree, BIT) handles both requests in O(log n) in the worst case, and its code is very short.

The lecture’s 16 numbers (slide 3): the sum on [6, 13] from prefix sums.

02A card trick with powers of two

The lecture starts with a trick. Think of a number from 1 to 60 and find it on six cards: card A lists the numbers whose sum of powers of two contains 1, card B those that contain 2, then 4, 8, 16 and 32. Add up the first numbers of the cards that show your number, and you get your number back.

Why it works: every whole number is a sum of distinct powers of two in exactly one way, and that sum is its binary form. 52 = 32 + 16 + 4, so 52 = 110100₂, and 52 appears exactly on the cards that start with 4, 16 and 32 (C, E and F). No other number gives the same set of cards, because two different numbers cannot have the same binary form.

Keep this fact in mind: the Fenwick tree is the same trick, applied to intervals.

03The idea: each index stores one interval

Intervals split the same way as numbers. 21 = 16 + 4 + 1, so [1, 21] = [1, 16] + [17, 20] + [21, 21]; 52 = 32 + 16 + 4, so [1, 52] = [1, 32] + [33, 48] + [49, 52]. Every prefix [1, i] splits into pieces whose lengths are the powers of two of i, and in only one way.

So index i stores the sum of as many elements as the smallest power of two in i: the interval of length i & −i that ends at i. Odd indices such as 21 store a single element; 52 stores four, the elements 49, 50, 51 and 52. In binary, the length is given by the lowest 1 bit of i together with the zeros to its right: 12 = 1100₂ stores [9, 12], 8 = 1000₂ stores [1, 8], 6 = 110₂ stores [5, 6].

The array is called tree[]; its indices start at 1 and it has exactly n cells, no more memory than the input itself.

Indices 1 to 16 and their intervals (slides 8 and 9). The three intervals of [1, 13] are highlighted.

04Query and update: the lowest 1 bit

Query (read): to cover [1, 52] we visit indices 52, 48 and 32. In binary 52 = 110100₂, 48 = 110000₂, 32 = 100000₂: each next index is the previous one with its lowest 1 bit cleared, until the number becomes 0. That is the same as subtracting, each time, the smallest power of two the number is made of.

Update: which intervals contain element 37? [37, 37], [37, 38], [33, 40], [33, 48], [1, 64], [1, 128] and so on. We reach them with the reverse walk: each time add the lowest 1 bit, 37 → 38 → 40 → 48 → 64 → 128.

How do we find the lowest 1 bit quickly? Most computers subtract by adding the two’s complement: invert every bit, then add 1. In −x every bit above the lowest 1 bit is inverted and that bit itself stays, so x & -x keeps exactly the lowest 1 bit. For 44 = 101100₂: −44 = 010011 + 1 = 010100₂, and 101100₂ & 010100₂ = 000100₂ = 4. So update goes 44 → 48 → 64, and read goes 44 → 40 → 32 → 0 (slide 14). Each loop runs at most log₂n + 1 times: O(log n).

05Build, the sum on [6, 13], and a linear build

Build (slide 15): start with a tree[] full of zeros and call update(i, a[i]) for i = 1, 2, …, 16. update(1, 3) puts 3 into tree[1], tree[2], tree[4], tree[8] and tree[16]; update(2, 1) adds 1 to tree[2], tree[4], tree[8] and tree[16]; and so on. The result is the table of slide 16: tree[] = 3 4 2 8 3 6 1 19 2 7 2 11 3 4 0 36.

Range sum (slide 16): compute two sums from the start and subtract. For [6, 13]: read(13) = tree[13] + tree[12] + tree[8] = 3 + 11 + 19 = 33, read(5) = tree[5] + tree[4] = 3 + 8 = 11, and 33 − 11 = 22.

Build in O(n) (slides 17 and 18): n updates cost O(n log n). Faster: copy the array into tree[], then for i = 1 to n add tree[i] to its direct parent j = i + (i & −i), if j ≤ n. The parent in turn passes its accumulated sum one level up, so every edge of the tree is processed exactly once.

The lecture ends with three extensions (slides 19 to 21): the minimum or maximum on a prefix [1..K] (but not on an arbitrary [L..R]), counting inversions in O(N log N) (walk left to right; read(x) tells how many earlier values are at most x, the other earlier values form inversions with x; then update(x, 1)), and a 2D Fenwick tree for sums over rectangles.

Top: the tree[] of slide 16 with the cells of read(13) and read(5). Bottom: every index passes its sum to its parent (slide 18).

The lecture's C++C++

update and read are the code of slide 13: update adds val to every cell whose interval contains idx, read adds up the cells that tile [1, idx]. MaxVal is n, and the sum on [l, r] is read(r) − read(l − 1). The build function is from slide 18: bit[] starts as a copy of the array, and each i passes its sum to its parent j = i + (i & −i).

// slide 13: build and update
void update(int idx ,int val) {
    while (idx <= MaxVal) {
        tree[idx] += val;
        idx += (idx & -idx);
    }
}
// slide 13: query
int read(int idx) {
    int sum = 0;
    while (idx > 0){
        sum += tree[idx];
        idx = idx - (idx & -idx);
    }
    return sum;
}
// slide 18: build in O(n)
void build(vector<long long>& bit, int n) {
    for (int i = 1; i <= n; i++) {
        int j = i + (i & -i);
        if (j <= n) {
            bit[j] += bit[i];
        }
    }
}

Cost at a glance

Update (update)O(log n)

Prefix sum (read)O(log n)

Sum on [l, r] = read(r) − read(l − 1)O(log n)

Build with n updatesO(n log n)

Build in linear timeO(n)

MemoryO(n)

Remember

tree[i] stores the sum of the interval of length i & −i that ends at i: the smallest power of two in i.
read clears the lowest 1 bit (idx −= idx & −idx), update adds it (idx += idx & −idx); both take O(log n).
A range sum is two prefix sums: sum[l, r] = read(r) − read(l − 1), as in [6, 13] = 33 − 11 = 22.

Watch

The lecture as a narrated explainer video.

▶

Watch the lecture, animated

The video follows the lecture slide by slide: the same example, the same notation. Use it before or after playing with the visualizer.

▶ Open the video page ▣ Open as presentation

More from the lectures▶ SQRT decomposition

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Watch the binary panel: the amber ring marks idx & −idx. update adds it to idx, read subtracts it. Then enter your own array and an update such as "7 +3" to see the same query again after the change.

Interactive visualizerfocus here, then space ← →

Fenwick tree

query: [6, 13]

The lecture’s array of 16 numbers. tree[] starts with zeros. Build: call update(i, a[i]) for every i from 1 to 16, as on slide 15.

Pseudocode

 1 void update(int idx, int val) { 2   while (idx <= MaxVal) { 3     tree[idx] += val; 4     idx += (idx & -idx); 5   } 6 } 7 int read(int idx) { 8   int sum = 0; 9   while (idx > 0) {10     sum += tree[idx];11     idx = idx - (idx & -idx);12   }13   return sum;14 }15 sum[l, r] = read(r) - read(l - 1)

1 / 1

Check

Three questions. Pick an answer to see why.

What is 40 & −40?

Which cells does read(11) add up?

Which interval does tree[24] cover?

Practice

Real problems to lock it in, easiest first.

CSESDynamic Range Sum Queries beginner↗CodeforcesDistinct Characters Queries intermediate↗SPOJMatrix Summation (MATSUM) intermediate↗CodeforcesNested Segments advanced↗CodeforcesEnemy is weak advanced↗