Fenwick tree
The Fenwick tree (binary indexed tree) keeps prefix sums under point updates in O(log n) per operation, using nothing more than an array and the lowest set bit of an index.
Learning goals
- Explain which range of the array each Fenwick cell is responsible for
- Use the lowest set bit to climb for updates and to descend for queries
- Implement point update, prefix sum, range sum and the O(n) build
- State why every operation takes O(log n) steps
Prerequisites
A prefix-sum array answers range sums in O(1) but needs O(n) work to change one value. A plain array changes in O(1) but needs O(n) per sum. The Fenwick tree balances the two at O(log n) each, in an array as small as the input.
Binary indexed tree
A Fenwick tree for n values is an array tree[1..n]. Cell i stores the sum of the lowbit(i) values that end at position i, where lowbit(i) is the value of the lowest set bit of i. So tree[8] covers 8 values (1..8), tree[6] covers 2 values (5..6), and every odd cell covers just itself. Positions are 1-based: index 0 is unused, which is what makes the bit trick work.
The animation shows the array a on top and the tree cells below it, each labelled with the range it covers. The default input is 3, 2, -1, 6, 5, 4, -3, 3, and the tree is 3, 5, -1, 10, 5, 9, -3, 19: for example tree[4] = 3 + 2 - 1 + 6 = 10 and tree[8] is the sum of all eight values, 19.
1class Fenwick {2final long[] tree; // 1-based: tree[i] covers the lowbit(i) values ending at position i3Fenwick(int n) { tree = new long[n + 1]; } // tree[0] is unused4static int[] covers(int i) { // the positions tree[i] adds up: {first, last}5return new int[]{i - (i & -i) + 1, i};6}7}
Fenwick tree (binary indexed tree): build, update, prefix and range sums
Interactive · edit the inputa[i], i = 1..n
bit[i] = sum of a over the range shown under it
The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6.
1int[] bit = new int[n + 1]; // 1-based: bit[i] covers the lowbit(i) values ending at i2void update(int i, int delta) { // a[i] += delta, i is 1-based3for (; i <= n; i += i & -i) bit[i] += delta; // climb: add the lowest set bit4}5int prefix(int i) { // sum of a[1..i]6int s = 0;7for (; i > 0; i -= i & -i) s += bit[i]; // descend: strip the lowest set bit8return s;9}10int range(int l, int r) { return prefix(r) - prefix(l - 1); }11void buildLinear(int[] a) { // O(n) build12for (int i = 1; i <= n; i++) {13bit[i] += a[i];14int j = i + (i & -i); // the next cell that covers i15if (j <= n) bit[j] += bit[i];16}17}
Live state
n
8
Execution trace (dry run table)Show 4 stepsHide
| Step | Line | State | What happens |
|---|---|---|---|
| 1 | L1 | n=8 | The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6. |
| 2 | L7 | i=6 binary=110 i & -i=2 sum=9 | prefix(6): add bit[6] = 9 (covers 5..6). Next i = 6 - 2 = 4. |
| 3 | L7 | i=4 binary=100 i & -i=4 sum=19 | prefix(6): add bit[4] = 10 (covers 1..4). Next i = 4 - 4 = 0: done. |
| 4 | L8 | return=19 cells touched=2 | prefix(6) = 19: the sum of a[1..6] from 2 cells, because the ranges of the visited cells tile 1..6 exactly. |
Lowest set bit
The lowest set bit of i is i & -i. In two's complement, -i is ~i + 1: flipping all bits and adding 1 carries through the trailing zeros and stops at the lowest 1, so the AND keeps only that bit. For example 12 = 1100 and -12 = ...10100, so 12 & -12 = 100 = 4.
Two moves on an index use it. Adding the lowest bit, i + lowbit(i), goes to the next cell whose range contains position i (used by updates). Subtracting it, i - lowbit(i), removes the range of cell i and leaves the cell just before it (used by queries). Each move changes the number of trailing zeros or the number of set bits in a way that bounds the number of steps by log n.
| i | binary | lowbit(i) | tree[i] covers | set bits (prefix steps) | update steps (n = 8) |
|---|---|---|---|---|---|
| 1 | 001 | 1 | 1..1 | 1 | 4 |
| 2 | 010 | 2 | 1..2 | 1 | 3 |
| 3 | 011 | 1 | 3..3 | 2 | 3 |
| 4 | 100 | 4 | 1..4 | 1 | 2 |
| 5 | 101 | 1 | 5..5 | 2 | 3 |
| 6 | 110 | 2 | 5..6 | 2 | 2 |
| 7 | 111 | 1 | 7..7 | 3 | 2 |
| 8 | 1000 | 8 | 1..8 | 1 | 1 |
1static int lowbit(int i) { return i & -i; } // the lowest set bit, as a number2static int nextToUpdate(int i) { return i + lowbit(i); } // the next cell whose range contains i3static int nextToRead(int i) { return i - lowbit(i); } // the cell just before the range of i
Fenwick tree (binary indexed tree): build, update, prefix and range sums
Interactive · edit the inputa[i], i = 1..n
bit[i] = sum of a over the range shown under it
The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6.
1int[] bit = new int[n + 1]; // 1-based: bit[i] covers the lowbit(i) values ending at i2void update(int i, int delta) { // a[i] += delta, i is 1-based3for (; i <= n; i += i & -i) bit[i] += delta; // climb: add the lowest set bit4}5int prefix(int i) { // sum of a[1..i]6int s = 0;7for (; i > 0; i -= i & -i) s += bit[i]; // descend: strip the lowest set bit8return s;9}10int range(int l, int r) { return prefix(r) - prefix(l - 1); }11void buildLinear(int[] a) { // O(n) build12for (int i = 1; i <= n; i++) {13bit[i] += a[i];14int j = i + (i & -i); // the next cell that covers i15if (j <= n) bit[j] += bit[i];16}17}
Live state
n
8
Execution trace (dry run table)Show 4 stepsHide
| Step | Line | State | What happens |
|---|---|---|---|
| 1 | L1 | n=8 | The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6. |
| 2 | L7 | i=6 binary=110 i & -i=2 sum=9 | prefix(6): add bit[6] = 9 (covers 5..6). Next i = 6 - 2 = 4. |
| 3 | L7 | i=4 binary=100 i & -i=4 sum=19 | prefix(6): add bit[4] = 10 (covers 1..4). Next i = 4 - 4 = 0: done. |
| 4 | L8 | return=19 cells touched=2 | prefix(6) = 19: the sum of a[1..6] from 2 cells, because the ranges of the visited cells tile 1..6 exactly. |
Point update
To add delta to position i, every cell whose range contains i must change. Those cells are i, i + lowbit(i), then again, and so on until the index passes n: each step moves to the smallest larger cell that also covers i. The loop is one line.
Try the preset "Point update" (add 5 to index 2, which is position 3): cells 3, 4 and 8 change, because those are the only cells whose ranges include position 3. The animation highlights the changed cells and prints the next index at each step. Setting a value, rather than adding, is the same operation with delta = newValue - oldValue.
1class Fenwick {2final long[] tree;3final int n;4Fenwick(int n) { this.n = n; tree = new long[n + 1]; }5void update(int i, long delta) { // a[i] += delta, i is 1-based6for (; i <= n; i += i & -i) tree[i] += delta; // climb: add the lowest set bit7}8}
Best
O(1)
Average
O(log n)
Worst
O(log n)
Space
O(1)
Fenwick tree (binary indexed tree): build, update, prefix and range sums
Interactive · edit the inputa[i], i = 1..n
bit[i] = sum of a over the range shown under it
The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6.
1int[] bit = new int[n + 1]; // 1-based: bit[i] covers the lowbit(i) values ending at i2void update(int i, int delta) { // a[i] += delta, i is 1-based3for (; i <= n; i += i & -i) bit[i] += delta; // climb: add the lowest set bit4}5int prefix(int i) { // sum of a[1..i]6int s = 0;7for (; i > 0; i -= i & -i) s += bit[i]; // descend: strip the lowest set bit8return s;9}10int range(int l, int r) { return prefix(r) - prefix(l - 1); }11void buildLinear(int[] a) { // O(n) build12for (int i = 1; i <= n; i++) {13bit[i] += a[i];14int j = i + (i & -i); // the next cell that covers i15if (j <= n) bit[j] += bit[i];16}17}
Live state
n
8
Execution trace (dry run table)Show 4 stepsHide
| Step | Line | State | What happens |
|---|---|---|---|
| 1 | L1 | n=8 | The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6. |
| 2 | L7 | i=6 binary=110 i & -i=2 sum=9 | prefix(6): add bit[6] = 9 (covers 5..6). Next i = 6 - 2 = 4. |
| 3 | L7 | i=4 binary=100 i & -i=4 sum=19 | prefix(6): add bit[4] = 10 (covers 1..4). Next i = 4 - 4 = 0: done. |
| 4 | L8 | return=19 cells touched=2 | prefix(6) = 19: the sum of a[1..6] from 2 cells, because the ranges of the visited cells tile 1..6 exactly. |
Prefix sum
The sum of the first i values is built from the cells you reach by removing the lowest bit repeatedly: i, i - lowbit(i), and so on down to 0. The ranges of these cells are consecutive and do not overlap, so they tile 1..i exactly. For i = 7 = 111 the cells are 7 (covers 7), 6 (covers 5..6) and 4 (covers 1..4).
The preset "Prefix sum" asks for the first 7 values of 3, 2, -1, 6, 5, 4, -3, 3: the animation reads 3 cells and adds -3 + 9 + 10 = 16. The number of cells read is the number of set bits of i, at most the bit length of n.
1class Fenwick {2final long[] tree;3final int n;4Fenwick(int n) { this.n = n; tree = new long[n + 1]; }5void update(int i, long delta) {6for (; i <= n; i += i & -i) tree[i] += delta;7}8long prefix(int i) { // sum of a[1..i]9long s = 0;10for (; i > 0; i -= i & -i) s += tree[i]; // descend: strip the lowest set bit11return s;12}13}
Best
O(1)
Average
O(log n)
Worst
O(log n)
Space
O(1)
Fenwick tree (binary indexed tree): build, update, prefix and range sums
Interactive · edit the inputa[i], i = 1..n
bit[i] = sum of a over the range shown under it
The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6.
1int[] bit = new int[n + 1]; // 1-based: bit[i] covers the lowbit(i) values ending at i2void update(int i, int delta) { // a[i] += delta, i is 1-based3for (; i <= n; i += i & -i) bit[i] += delta; // climb: add the lowest set bit4}5int prefix(int i) { // sum of a[1..i]6int s = 0;7for (; i > 0; i -= i & -i) s += bit[i]; // descend: strip the lowest set bit8return s;9}10int range(int l, int r) { return prefix(r) - prefix(l - 1); }11void buildLinear(int[] a) { // O(n) build12for (int i = 1; i <= n; i++) {13bit[i] += a[i];14int j = i + (i & -i); // the next cell that covers i15if (j <= n) bit[j] += bit[i];16}17}
Live state
n
8
Execution trace (dry run table)Show 4 stepsHide
| Step | Line | State | What happens |
|---|---|---|---|
| 1 | L1 | n=8 | The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6. |
| 2 | L7 | i=6 binary=110 i & -i=2 sum=9 | prefix(6): add bit[6] = 9 (covers 5..6). Next i = 6 - 2 = 4. |
| 3 | L7 | i=4 binary=100 i & -i=4 sum=19 | prefix(6): add bit[4] = 10 (covers 1..4). Next i = 4 - 4 = 0: done. |
| 4 | L8 | return=19 cells touched=2 | prefix(6) = 19: the sum of a[1..6] from 2 cells, because the ranges of the visited cells tile 1..6 exactly. |
Range sum
A range sum is the difference of two prefix sums: sum(l..r) = prefix(r) - prefix(l - 1). Because the structure only knows prefixes, any operation that is invertible, such as sum, XOR or counting, fits; operations without an inverse, such as minimum, do not (segment trees handle those).
Use the preset "Range sum" (positions 3 to 6): the animation computes prefix(6) = 19 and prefix(2) = 5, so the sum is 14. For l = 1 the second prefix is prefix(0) = 0, an empty loop, which is why the 1-based layout with an unused cell 0 is convenient.
1class Fenwick {2final long[] tree;3final int n;4Fenwick(int n) { this.n = n; tree = new long[n + 1]; }5void update(int i, long delta) {6for (; i <= n; i += i & -i) tree[i] += delta;7}8long prefix(int i) {9long s = 0;10for (; i > 0; i -= i & -i) s += tree[i];11return s;12}13long rangeSum(int l, int r) { return prefix(r) - prefix(l - 1); } // 1-based, inclusive14}
Fenwick tree (binary indexed tree): build, update, prefix and range sums
Interactive · edit the inputa[i], i = 1..n
bit[i] = sum of a over the range shown under it
The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6.
1int[] bit = new int[n + 1]; // 1-based: bit[i] covers the lowbit(i) values ending at i2void update(int i, int delta) { // a[i] += delta, i is 1-based3for (; i <= n; i += i & -i) bit[i] += delta; // climb: add the lowest set bit4}5int prefix(int i) { // sum of a[1..i]6int s = 0;7for (; i > 0; i -= i & -i) s += bit[i]; // descend: strip the lowest set bit8return s;9}10int range(int l, int r) { return prefix(r) - prefix(l - 1); }11void buildLinear(int[] a) { // O(n) build12for (int i = 1; i <= n; i++) {13bit[i] += a[i];14int j = i + (i & -i); // the next cell that covers i15if (j <= n) bit[j] += bit[i];16}17}
Live state
n
8
Execution trace (dry run table)Show 4 stepsHide
| Step | Line | State | What happens |
|---|---|---|---|
| 1 | L1 | n=8 | The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6. |
| 2 | L7 | i=6 binary=110 i & -i=2 sum=9 | prefix(6): add bit[6] = 9 (covers 5..6). Next i = 6 - 2 = 4. |
| 3 | L7 | i=4 binary=100 i & -i=4 sum=19 | prefix(6): add bit[4] = 10 (covers 1..4). Next i = 4 - 4 = 0: done. |
| 4 | L8 | return=19 cells touched=2 | prefix(6) = 19: the sum of a[1..6] from 2 cells, because the ranges of the visited cells tile 1..6 exactly. |
Linear build
Building the tree with n separate updates costs O(n log n). A linear build does it in O(n): put a[i] into tree[i], then, going upward, add each finished cell into the one cell that covers it next, i + lowbit(i). When the loop reaches i, every cell below i that belongs to i's range has already been added, so tree[i] is final and can be pushed on.
Compare the presets "Build by updates" and "Linear build" on the same array: both end with 3, 5, -1, 10, 5, 9, -3, 19, but the first makes 20 cell updates and the second pushes each cell once. For one build the difference is a log factor; it matters for large inputs such as 10^6 values.
1class Fenwick {2final long[] tree;3final int n;4Fenwick(long[] a) { // a is 0-based; the tree is built in O(n)5n = a.length;6tree = new long[n + 1];7for (int i = 1; i <= n; i++) {8tree[i] += a[i - 1];9int parent = i + (i & -i); // the next cell that covers i10if (parent <= n) tree[parent] += tree[i];11}12}13long prefix(int i) {14long s = 0;15for (; i > 0; i -= i & -i) s += tree[i];16return s;17}18}
Fenwick tree (binary indexed tree): build, update, prefix and range sums
Interactive · edit the inputa[i], i = 1..n
bit[i] = sum of a over the range shown under it
The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6.
1int[] bit = new int[n + 1]; // 1-based: bit[i] covers the lowbit(i) values ending at i2void update(int i, int delta) { // a[i] += delta, i is 1-based3for (; i <= n; i += i & -i) bit[i] += delta; // climb: add the lowest set bit4}5int prefix(int i) { // sum of a[1..i]6int s = 0;7for (; i > 0; i -= i & -i) s += bit[i]; // descend: strip the lowest set bit8return s;9}10int range(int l, int r) { return prefix(r) - prefix(l - 1); }11void buildLinear(int[] a) { // O(n) build12for (int i = 1; i <= n; i++) {13bit[i] += a[i];14int j = i + (i & -i); // the next cell that covers i15if (j <= n) bit[j] += bit[i];16}17}
Live state
n
8
Execution trace (dry run table)Show 4 stepsHide
| Step | Line | State | What happens |
|---|---|---|---|
| 1 | L1 | n=8 | The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6. |
| 2 | L7 | i=6 binary=110 i & -i=2 sum=9 | prefix(6): add bit[6] = 9 (covers 5..6). Next i = 6 - 2 = 4. |
| 3 | L7 | i=4 binary=100 i & -i=4 sum=19 | prefix(6): add bit[4] = 10 (covers 1..4). Next i = 4 - 4 = 0: done. |
| 4 | L8 | return=19 cells touched=2 | prefix(6) = 19: the sum of a[1..6] from 2 cells, because the ranges of the visited cells tile 1..6 exactly. |
O(log n) operations
Both loops take at most about log2 n steps. A prefix query takes one step per set bit of i, which is at most the bit length of n. An update step adds the lowest set bit, which makes the number of trailing zeros of i strictly larger, so after at most the bit length of n steps the index passes n. For n = 8 every operation needs between 1 and 4 steps; see the last two columns of the table in the lowest-set-bit item.
In practice the Fenwick tree is very fast: a tight loop over one array, no recursion, no allocation. Its limits are the same as its strengths: it needs an invertible operation for ranges, and it supports point updates directly; range updates need the variants of the next lesson.
| Operation | Steps | Why |
|---|---|---|
| prefix(i) | bitCount(i) ≤ ⌊log2 n⌋ + 1 | each step clears one set bit of i |
| update(i, delta) | ≤ ⌊log2 n⌋ + 1 | each step raises the position of the lowest set bit |
| rangeSum(l, r) | two prefix queries | prefix(r) - prefix(l - 1) |
| build (updates) | n × O(log n) | n point updates |
| build (linear) | n | each cell is pushed to its parent once |
1static int prefixSteps(int i) { return Integer.bitCount(i); } // one step per set bit of i2static int updateSteps(int i, int n) {3int steps = 0;4for (; i <= n; i += i & -i) steps++;5return steps;6}
Fenwick tree (binary indexed tree): build, update, prefix and range sums
Interactive · edit the inputa[i], i = 1..n
bit[i] = sum of a over the range shown under it
The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6.
1int[] bit = new int[n + 1]; // 1-based: bit[i] covers the lowbit(i) values ending at i2void update(int i, int delta) { // a[i] += delta, i is 1-based3for (; i <= n; i += i & -i) bit[i] += delta; // climb: add the lowest set bit4}5int prefix(int i) { // sum of a[1..i]6int s = 0;7for (; i > 0; i -= i & -i) s += bit[i]; // descend: strip the lowest set bit8return s;9}10int range(int l, int r) { return prefix(r) - prefix(l - 1); }11void buildLinear(int[] a) { // O(n) build12for (int i = 1; i <= n; i++) {13bit[i] += a[i];14int j = i + (i & -i); // the next cell that covers i15if (j <= n) bit[j] += bit[i];16}17}
Live state
n
8
Execution trace (dry run table)Show 4 stepsHide
| Step | Line | State | What happens |
|---|---|---|---|
| 1 | L1 | n=8 | The Fenwick tree for a = [3, 2, -1, 6, 5, 4, -3, 3]. bit[i] holds the sum of the lowbit(i) values ending at position i (shown under each cell). Positions are 1-based: index 5 of the input is i = 6. |
| 2 | L7 | i=6 binary=110 i & -i=2 sum=9 | prefix(6): add bit[6] = 9 (covers 5..6). Next i = 6 - 2 = 4. |
| 3 | L7 | i=4 binary=100 i & -i=4 sum=19 | prefix(6): add bit[4] = 10 (covers 1..4). Next i = 4 - 4 = 0: done. |
| 4 | L8 | return=19 cells touched=2 | prefix(6) = 19: the sum of a[1..6] from 2 cells, because the ranges of the visited cells tile 1..6 exactly. |
Practice ladder
Now try it yourself
Easy
- Range Sum Query - Immutable
- Range Sum Query - Mutable
Medium
- Count of Smaller Numbers After Self
- Create Sorted Array through Instructions
Advanced
- Count of Range Sum
- Reverse Pairs
Key takeaways
- tree[i] holds the sum of the lowbit(i) values that end at i; the lowest set bit is i & -i.
- Update climbs with i += lowbit(i); query descends with i -= lowbit(i); both take O(log n) steps.
- Range sum = prefix(r) - prefix(l - 1); the structure needs an invertible operation, and builds in O(n).