Fenwick Trees (Binary Indexed Trees)
Why this exists
A prefix-sum array answers range sums in but needs to absorb one update. A segment tree does both in , at the cost of to cells and a page of code. For the most common case — sums (or any invertible operation) with point updates — there is something smaller and faster: an array of numbers and two loops of three lines each, in which index arithmetic on the binary representation of does all the work. That is the Fenwick tree, also called the binary indexed tree (BIT).
Peter Fenwick published it in 1994 as "A New Data Structure for Cumulative Frequency Tables" (Software: Practice and Experience 24(3)), to solve a concrete problem in data compression: an adaptive arithmetic coder must, for every symbol it encodes, look up the cumulative frequency of all smaller symbols and then increment that symbol's count. With an alphabet of a few hundred symbols and millions of symbols to encode, both operations had to be fast. A similar structure had appeared earlier in Boris Ryabko's 1989 work on fast adaptive coding, which is why you will occasionally see it credited to both. Competitive programmers adopted it in the late 1990s because it is the shortest correct code for dynamic prefix sums, and it has stayed there.
This lesson builds the Fenwick tree from its one idea — each cell is responsible for a block whose length is the lowest set bit of its index — and proves why i & -i steps through exactly the right cells in both directions. Then it extends the structure in the directions that matter: construction, range updates with point queries, range updates with range queries using two trees (with the formula derived rather than memorized), finding the k-th element by binary lifting, the 2D BIT, and inversion counting with coordinate compression. It closes with an honest comparison against segment trees, including the things a Fenwick tree simply cannot do. The Fenwick section of Advanced Data Structures and the short overview in Trees are the quick versions.
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| Prefix or range sums with point updates interleaved | Fenwick tree: add(i, d) and prefix(i) |
| "count elements smaller than x seen so far", "count smaller after self" | BIT over values (compressed), sweep in order |
| "number of inversions", "pairs i < j with a[i] > a[j]" | BIT inversion counting, |
| "add v to [l, r]" and "value at position i" | BIT over the difference array (range update, point query) |
| "add v to [l, r]" and "sum of [l, r]" | Two BITs: |
| "k-th smallest in a dynamic multiset", "k-th remaining element" | Count BIT + binary lifting descent, |
| Rectangle sums with point updates on a grid | 2D BIT, |
| Offline queries "distinct values in [l, r]" | Sort queries by right end, BIT over last occurrences |
| Cumulative frequencies for an adaptive model (compression) | The original use case |
| Range minimum/maximum with arbitrary updates | Not a Fenwick tree — use a segment tree |
| Range assign, max-subarray merges, descents with complex predicates | Not a Fenwick tree — use a segment tree |
The core trigger: prefix aggregates of an invertible operation under point updates. Sums and XOR qualify directly; counts are sums; products qualify over a field without zeros. Min and max do not, except in special one-directional cases discussed later.
Intuition & first principles
Every positive integer has a unique binary representation, so every prefix splits uniquely into blocks of power-of-two lengths, one block per set bit of , largest first. Take :
Block lengths 8, 4 and 1 are exactly the set bits of 13. If we had precomputed the sums of , and , the prefix sum of 13 would cost three additions. Each block ends at a "partial sum" of the bits: , , . So store, at index , the sum of the block that ends at and whose length is the lowest set bit of :
Then covers (lowbit 1), covers (lowbit 4), covers (lowbit 8). Walking means repeatedly removing the lowest set bit: .
Why i & -i is the lowest set bit. In two's complement, . Write (some high bits , then the lowest 1, then zeros). Then , and adding 1 carries through the ones: . ANDing with kills the high part (each bit of meets its complement) and keeps exactly . The bit manipulation lesson covers this trick and its relatives (i & (i - 1) clears the lowest bit, so i - (i & -i) == i & (i - 1)).
The update direction is the subtle part. When changes, which cells contain in their block? The answer, proved in the correctness section, is: itself, then , then that plus its lowbit, and so on — repeatedly adding the lowest set bit. For : . Every cell on that chain must absorb the change; no other cell contains .
So the whole data structure is: an array tree[1..n] and two loops, one that strips low bits (query) and one that adds them (update). Neither loop runs more than times.
Responsibility ranges for n = 16
Using a[1..16] = [5, 3, 7, 9, 6, 4, 1, 2, 8, 2, 5, 3, 7, 1, 4, 6]:
| i | binary | lowbit(i) | tree[i] covers | tree[i] |
|---|---|---|---|---|
| 1 | 00001 | 1 | a[1..1] | 5 |
| 2 | 00010 | 2 | a[1..2] | 8 |
| 3 | 00011 | 1 | a[3..3] | 7 |
| 4 | 00100 | 4 | a[1..4] | 24 |
| 5 | 00101 | 1 | a[5..5] | 6 |
| 6 | 00110 | 2 | a[5..6] | 10 |
| 7 | 00111 | 1 | a[7..7] | 1 |
| 8 | 01000 | 8 | a[1..8] | 37 |
| 9 | 01001 | 1 | a[9..9] | 8 |
| 10 | 01010 | 2 | a[9..10] | 10 |
| 11 | 01011 | 1 | a[11..11] | 5 |
| 12 | 01100 | 4 | a[9..12] | 18 |
| 13 | 01101 | 1 | a[13..13] | 7 |
| 14 | 01110 | 2 | a[13..14] | 8 |
| 15 | 01111 | 1 | a[15..15] | 4 |
| 16 | 10000 | 16 | a[1..16] | 73 |
Half of the cells (odd ) hold a single element, a quarter hold two, an eighth hold four, and so on: the same dyadic blocks as a segment tree, but only the blocks that end at each index, which is why cells suffice instead of .
flowchart BT
T1["tree[1]: a1"] --> T2["tree[2]: a1..a2"]
T3["tree[3]: a3"] --> T4["tree[4]: a1..a4"]
T2 --> T4
T5["tree[5]: a5"] --> T6["tree[6]: a5..a6"]
T6 --> T8["tree[8]: a1..a8"]
T7["tree[7]: a7"] --> T8
T4 --> T8
T8 --> T16["tree[16]: a1..a16"]
T12["tree[12]: a9..a12"] --> T16
T14["tree[14]: a13..a14"] --> T16
T15["tree[15]: a15"] --> T16
The arrows are the update edges : each cell's block is contained in its parent's block. (For readability only some of cells 9 to 15 are drawn; 9 feeds 10, 10 and 11 feed 12, 13 feeds 14.) The query edges form a different tree, rooted at 0, in which each step jumps to the cell holding the block immediately to the left.
Mechanics
Prefix query
prefix(i): s = 0
while i > 0:
s += tree[i]
i -= i & -i # strip the lowest set bit
return s
Range sum is the difference of two prefixes: sum(l, r) = prefix(r) - prefix(l - 1). This is where invertibility is used: subtraction undoes addition.
Trace: prefix(13) on the table above. The true prefix sum is .
| Step | i | binary | lowbit | tree[i] (covers) | running sum |
|---|---|---|---|---|---|
| 1 | 13 | 01101 | 1 | 7 (a[13..13]) | 7 |
| 2 | 12 | 01100 | 4 | 18 (a[9..12]) | 25 |
| 3 | 8 | 01000 | 8 | 37 (a[1..8]) | 62 |
| 4 | 0 | — | — | stop | 62 |
flowchart LR
Q["prefix(13)<br/>13 = 01101"] -->|"take tree[13] = a13"| S1["i = 12<br/>01100"]
S1 -->|"take tree[12] = a9..a12"| S2["i = 8<br/>01000"]
S2 -->|"take tree[8] = a1..a8"| S3["i = 0: stop<br/>sum = 7 + 18 + 37 = 62"]
Three steps, because 13 has three set bits. The worst case is (all ones): steps, e.g. 4 steps for .
Point update
add(i, delta): while i <= n:
tree[i] += delta
i += i & -i # move to the next cell whose block contains i
Trace: add(5, +3), generated by scripts/traces/fenwick_update.py (the visualizer above plays the same run).
| Step | i | binary | lowbit | tree[i] covers | tree[i] before → after | next i |
|---|---|---|---|---|---|---|
| 1 | 5 | 00101 | 1 | a[5..5] | 6 → 9 | 6 |
| 2 | 6 | 00110 | 2 | a[5..6] | 10 → 13 | 8 |
| 3 | 8 | 01000 | 8 | a[1..8] | 37 → 40 | 16 |
| 4 | 16 | 10000 | 16 | a[1..16] | 73 → 76 | 32 |
| 5 | 32 | — | — | 32 > n: stop |
Four cells touched: 5, 6, 8, 16 — precisely the cells in the table whose "covers" range contains 5. After the update, prefix(13) walks 13, 12, 8 again and returns .
O(n) construction
Calling add(i, a[i]) for every builds the tree in . There is a linear-time build that pushes each cell's finished value into its parent exactly once:
build(a): tree[i] = a[i] for all i
for i in 1..n:
j = i + (i & -i)
if j <= n: tree[j] += tree[i]
When the loop reaches , every cell that feeds into (all have smaller indices) has already added its total, so tree[i] is final and can be pushed to its parent. An equivalent formulation: tree[i] = P[i] - P[i - lowbit(i)] from an ordinary prefix-sum array .
Range update, point query
Flip the roles. Keep a BIT over the difference array , where . Adding to changes only (by ) and (by ): two point updates. Reading is a prefix sum of : one query. Both . This is the dynamic version of the static difference array.
Range update, range query: two BITs
Now we want both "add to " and "sum of ". Keep the difference array as before, and compute what a prefix sum of looks like in terms of :
Each is counted once for every from to , that is times. Split the factor:
Both sums on the right are prefix sums of something we can maintain with point updates: stores and stores . Then
A range add of on is and , so:
- :
add(l, x),add(r + 1, -x); - :
add(l, x * (l - 1)),add(r + 1, -x * r).
Four point updates per range update, two prefix queries per prefix sum, everything .
Check by hand on a = [5, 3, 7, 9, 6, 4, 1, 2] (1-based) with add(2, 6, +2). Both BITs start from of the original array (or, simpler, start at zero and keep the original prefix sums separately; the code below builds ). Expected new array [5, 5, 9, 11, 8, 6, 1, 2], so sum(1, 8) = 47, sum(1, 4) = 30, sum(4, 5) = 19. The tests in the implementation section assert exactly these values.
| Operation | point updates | point updates |
|---|---|---|
| range add +2 on [2, 6] | +2 at 2, −2 at 7 | +2·1 = +2 at 2, −2·6 = −12 at 7 |
For a prefix ending at , the two contributions to cancel and contributes , so the prefix sum gains : five elements, each +2. For it gains : exactly the elements from index 2 to , each +2. The formula is right in both regimes.
Finding the k-th element: binary lifting on the BIT
Suppose the BIT stores counts (how many copies of each value are present) and we want the smallest index with — the k-th smallest element of the multiset. Binary search over with a prefix query inside costs . The BIT's structure allows : build one bit at a time from the top.
lower_bound(k): pos = 0
for step in [highest power of 2 <= n, ..., 2, 1]:
if pos + step <= n and tree[pos + step] < k:
pos += step
k -= tree[pos]
return pos + 1
Why tree[pos + step] is the right thing to look at: pos is always a multiple of (its bits below the current step are zero), so pos + step has lowbit equal to step, and tree[pos + step] covers exactly — the next block of length step after the part already accepted. If that whole block's total is still less than the remaining , the answer lies beyond it: accept it. Otherwise the answer lies inside it: try a smaller step. This is binary search on the implicit tree, with no extra prefix queries.
Trace: after the update above (a[5] is now 9), find the smallest with . The prefix sums are now 5, 8, 15, 24, 33, 37, 38, 40, 48, …, so the answer should be 8.
| step | pos + step | tree[pos + step] | compare with k | action | pos | remaining k |
|---|---|---|---|---|---|---|
| 16 | 16 | 76 | 76 ≥ 40 | skip | 0 | 40 |
| 8 | 8 | 40 | 40 ≥ 40 | skip | 0 | 40 |
| 4 | 4 | 24 | 24 < 40 | take | 4 | 16 |
| 2 | 6 | 13 | 13 < 16 | take | 6 | 3 |
| 1 | 7 | 1 | 1 < 3 | take | 7 | 2 |
Result . Note the step-8 row: the block sums to exactly 40, which is not less than , so the answer is inside it — the strict comparison is what makes this a lower bound. This descent requires all values to be non-negative (otherwise prefix sums are not monotone and "the first index reaching " is not found by descent).
The 2D BIT
The same idea per dimension: tree[i][j] covers rows and columns . Update and query are two nested loops; each is . A rectangle sum is inclusion–exclusion over four prefix rectangles, exactly like the 2D prefix sums. Memory is ; for sparse grids use a hash map of rows or offline compression per row.
Inversion counting with coordinate compression
An inversion is a pair with . Sweep left to right; before inserting , the number of earlier elements greater than is "elements seen so far" minus "elements seen so far that are " — a prefix query on a BIT indexed by value. Then insert (add 1 at its value). .
Values can be large or negative, so first compress: replace each value by its rank among the distinct values (1-based). Order is all that matters for inversions, so ranks give the same answer, and the BIT needs only as many cells as distinct values.
Trace on a = [100, 7, 100, 3, 50]. Distinct sorted values [3, 7, 50, 100], so ranks are [4, 2, 4, 1, 3].
| j | a[j] | rank | seen so far | prefix(rank) = seen ≤ a[j] | new inversions | total |
|---|---|---|---|---|---|---|
| 0 | 100 | 4 | 0 | 0 | 0 | 0 |
| 1 | 7 | 2 | 1 | 0 | 1 | 1 |
| 2 | 100 | 4 | 2 | 2 | 0 | 1 |
| 3 | 3 | 1 | 3 | 0 | 3 | 4 |
| 4 | 50 | 3 | 4 | 2 | 2 | 6 |
Six inversions: (100, 7), (100, 3), (100, 50) from the first 100, (7, 3), and (100, 3), (100, 50) from the second. The two 100s are not an inversion because the comparison is strict, which is why the query uses " rank" and not " rank".
The ladder: brute force → better → optimal
Running problem: count inversions in an array of integers in .
Rung 1: check all pairs
Two nested loops. comparisons. Correct, hopeless at this size.
Rung 2: insertion into a sorted list
Maintain the elements seen so far in a sorted Python list or vector. For each new element, binary-search its position: the count of greater elements is len - bisect_right(x). Then insert. The search is , but the insertion shifts up to elements: worst case overall. In practice memmove makes it surprisingly fast (a few seconds in C for ), but it is still quadratic.
Rung 3: merge sort
Count inversions during merge sort: whenever an element from the right half is emitted before remaining elements of the left half, it forms an inversion with each of them. , no extra structure. This is the classic textbook answer (CLRS problem 2-4) and is fully competitive.
Rung 4: Fenwick tree over compressed values
Compress, then sweep with a BIT. for the sort plus for BIT operations. The same constant class as merge sort, but online: you can answer "how many earlier elements exceed this one" for each as it arrives, and the same code extends to counting pairs with arbitrary value conditions ("earlier and smaller", "earlier and at least twice as large", triples via two sweeps) where merge sort gets awkward.
| Rung | Time | Extra space | Online? | Generalizes to |
|---|---|---|---|---|
| All pairs | Yes | Anything, slowly | ||
| Sorted list + bisect | worst, fast constant | Yes | Rank queries on insert-only sets | |
| Merge sort | No | Pair counts expressible during merges | ||
| Fenwick + compression | Yes (values known) | Rank queries with inserts and deletes, k-th element, 2D |
For the general dynamic problem — point updates and prefix sums — the ladder is the one from the segment tree lesson (array, prefix sums, sqrt decomposition, segment tree), and the Fenwick tree is the last rung for invertible operations: same asymptotics as a segment tree, about half the memory of the iterative segment tree, and the simplest loop.
Correctness
Responsibility ranges partition every prefix
Claim. For every , the query loop visits indices with , and the blocks are disjoint and their union is exactly .
Proof. By definition covers . Consecutive blocks share endpoints in the half-open sense: block starts right after , and block ends at . So the blocks tile without gaps or overlaps. The loop ends when , so the union is . Each step clears one set bit, so .
The update chain finds exactly the cells containing p
Claim. For , the cells whose block contains are exactly the terms of the sequence , .
Proof. Fix a bit position and consider the cells whose lowbit is . They are the numbers for , with blocks
These blocks, for , are disjoint (each occupies the first half of a length- window). So at most one cell with lowbit contains , and it exists exactly when falls in the first half of its window — when , written in binary, has a 0 at bit . In that case the cell is .
Now look at the sequence. Let be the positions of the zero bits of , and let denote the cell for from the previous paragraph. Write ; then , which is . Inductively, suppose : its bits above are those of , bit is 1, and the bits below are 0, so . Adding carries through bit and through the run of ones of between and , clearing them, and stops by setting bit . The result keeps the bits of above , has a 1 at and zeros below: that is . So the sequence enumerates the cells for all zero bits of , in increasing order, which by the previous paragraph are all the cells containing . It stops once the index exceeds , and since indices increase, no later term can be .
Worked check with : , zero bits at positions 0, 1, 3, 4. The cells are (), (), (), () — exactly the chain in the trace.
Consequence. After add(p, δ) every cell's stored sum is still the true sum of its block: the cells whose block contains gained , as did their true sums, and no other block contains . Combined with the partition claim, prefix(i) returns after any sequence of updates.
The O(n) build
Process from 1 to . Invariant: when the loop reaches , tree[i] equals the true block sum of . The block of is plus the blocks of the cells with (the update-tree children of , all smaller than ), because those child blocks tile . Each child already pushed its final value into tree[i] when the loop passed it.
Binary lifting
Invariant. Before processing step, pos is a multiple of , , the remaining equals , and the answer lies in (or beyond initially). Since is a multiple of , cell has lowbit exactly step, so its block is . If its sum is , the answer is beyond it and accepting keeps the invariant; otherwise the answer is within it and declining keeps the invariant with the window halved. After step 1 the window has length 1: the answer is . Non-negativity guarantees prefix sums are monotone, which the window argument needs.
Complexity
| Operation | Time | Notes |
|---|---|---|
prefix(i) | exactly popcount() iterations | |
add(i, δ) | number of zero bits of below | |
| range sum | two prefixes | |
| build by repeated add | ||
| linear build | each cell pushes once | |
| range add + point query | each | one BIT over differences |
| range add + range sum | each | two BITs, 4 updates / 2 queries |
| k-th element (lower bound) | binary lifting, non-negative values | |
| 2D update / query | memory | |
| Space | cells | no pointers, no tags |
Best case for a query is one iteration (powers of two), worst case ; on average about half the bits are set, so a prefix query does roughly iterations, and a random update similarly.
Constants and cache. Each iteration is one load, one add and one bit trick, with no branches besides the loop condition and no recursion. For 64-bit sums the BIT is 8 MB versus 16 MB for an iterative segment tree and 32 MB for a recursive one. The access pattern is not cache-friendly in an absolute sense (indices jump by powers of two, so the large-stride cells near the top are touched by many operations and stay cached, while the leaves are scattered), but in benchmarks the BIT is typically the fastest dynamic prefix-sum structure, often by a factor of 1.5–3 over a recursive segment tree. Treat that factor as indicative, not guaranteed; measure on your hardware (see benchmarks).
Implementation
The canonical Fenwick tree
One-based internally, with add, prefix, range_sum, a linear-time build and lower_bound by binary lifting. Every version replays the traces above (prefix 62, update touching 5/6/8/16, prefix 65 afterwards, lower bound 8 for ) and then checks 2,000 random operations against a brute-force array.
class Fenwick:
"""1-based Fenwick tree over n positions."""
def __init__(self, n: int) -> None:
self.n = n
self.tree = [0] * (n + 1)
@classmethod
def build(cls, a: list[int]) -> "Fenwick": # a is 0-based, O(n)
fw = cls(len(a))
t = fw.tree
for i in range(1, fw.n + 1):
t[i] += a[i - 1]
j = i + (i & -i)
if j <= fw.n:
t[j] += t[i]
return fw
def add(self, i: int, delta: int) -> list[int]:
touched = []
while i <= self.n:
self.tree[i] += delta
touched.append(i)
i += i & -i
return touched
def prefix(self, i: int) -> int:
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def range_sum(self, l: int, r: int) -> int:
return self.prefix(r) - self.prefix(l - 1)
def lower_bound(self, k: int) -> int:
"""Smallest i with prefix(i) >= k (values must be non-negative); n + 1 if none."""
pos, step = 0, 1 << self.n.bit_length()
while step:
nxt = pos + step
if nxt <= self.n and self.tree[nxt] < k:
pos = nxt
k -= self.tree[nxt]
step >>= 1
return pos + 1
if __name__ == "__main__":
a = [5, 3, 7, 9, 6, 4, 1, 2, 8, 2, 5, 3, 7, 1, 4, 6]
fw = Fenwick.build(a)
assert fw.tree[1:] == [5, 8, 7, 24, 6, 10, 1, 37, 8, 10, 5, 18, 7, 8, 4, 73]
assert fw.prefix(13) == 62 and fw.range_sum(5, 8) == 13
assert fw.add(5, 3) == [5, 6, 8, 16]
assert fw.prefix(13) == 65 and fw.lower_bound(40) == 8
assert fw.lower_bound(1) == 1 and fw.lower_bound(76) == 16 and fw.lower_bound(77) == 17
seed, n = 42, 37
def rnd() -> int:
global seed
seed = seed * 48271 % 2147483647
return seed
brute = [rnd() % 100 for _ in range(n)]
fw = Fenwick.build(brute)
for _ in range(2000):
if rnd() % 2 == 0:
p, d = rnd() % n, rnd() % 100
fw.add(p + 1, d)
brute[p] += d
else:
l, r = rnd() % n, rnd() % n
l, r = min(l, r), max(l, r)
assert fw.range_sum(l + 1, r + 1) == sum(brute[l:r + 1])
k = rnd() % (sum(brute) + 1) + 1
prefix, expect = 0, n + 1
for i, v in enumerate(brute, 1):
prefix += v
if prefix >= k:
expect = i
break
assert fw.lower_bound(k) == expect
print("fenwick ok")
import java.util.ArrayList;
import java.util.List;
public class Fenwick {
private final int n;
private final long[] tree;
Fenwick(int n) {
this.n = n;
this.tree = new long[n + 1];
}
static Fenwick build(long[] a) { // a is 0-based, O(n)
Fenwick fw = new Fenwick(a.length);
for (int i = 1; i <= fw.n; i++) {
fw.tree[i] += a[i - 1];
int j = i + (i & -i);
if (j <= fw.n) fw.tree[j] += fw.tree[i];
}
return fw;
}
List<Integer> add(int i, long delta) {
List<Integer> touched = new ArrayList<>();
for (; i <= n; i += i & -i) {
tree[i] += delta;
touched.add(i);
}
return touched;
}
long prefix(int i) {
long s = 0;
for (; i > 0; i -= i & -i) s += tree[i];
return s;
}
long rangeSum(int l, int r) {
return prefix(r) - prefix(l - 1);
}
int lowerBound(long k) { // smallest i with prefix(i) >= k; n + 1 if none
int pos = 0;
for (int step = Integer.highestOneBit(n) << 1; step > 0; step >>= 1) {
int nxt = pos + step;
if (nxt <= n && tree[nxt] < k) {
pos = nxt;
k -= tree[nxt];
}
}
return pos + 1;
}
static long seed = 42;
static long next() {
seed = seed * 48271 % 2147483647L;
return seed;
}
private static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
long[] a = {5, 3, 7, 9, 6, 4, 1, 2, 8, 2, 5, 3, 7, 1, 4, 6};
Fenwick fw = build(a);
long[] expectTree = {5, 8, 7, 24, 6, 10, 1, 37, 8, 10, 5, 18, 7, 8, 4, 73};
for (int i = 1; i <= 16; i++) check(fw.tree[i] == expectTree[i - 1], "build " + i);
check(fw.prefix(13) == 62 && fw.rangeSum(5, 8) == 13, "prefix");
check(fw.add(5, 3).equals(List.of(5, 6, 8, 16)), "touched");
check(fw.prefix(13) == 65 && fw.lowerBound(40) == 8, "after");
check(fw.lowerBound(1) == 1 && fw.lowerBound(76) == 16 && fw.lowerBound(77) == 17, "bounds");
int n = 37;
long[] brute = new long[n];
for (int i = 0; i < n; i++) brute[i] = next() % 100;
fw = build(brute.clone());
for (int it = 0; it < 2000; it++) {
if (next() % 2 == 0) {
int p = (int) (next() % n);
long d = next() % 100;
fw.add(p + 1, d);
brute[p] += d;
} else {
int l = (int) (next() % n), r = (int) (next() % n);
if (l > r) { int tmp = l; l = r; r = tmp; }
long expect = 0, total = 0;
for (int i = l; i <= r; i++) expect += brute[i];
check(fw.rangeSum(l + 1, r + 1) == expect, "range");
for (long v : brute) total += v;
long k = next() % (total + 1) + 1, prefix = 0;
int want = n + 1;
for (int i = 0; i < n; i++) {
prefix += brute[i];
if (prefix >= k) { want = i + 1; break; }
}
check(fw.lowerBound(k) == want, "lower bound");
}
}
System.out.println("fenwick ok");
}
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
class Fenwick {
int n;
std::vector<long long> tree;
public:
explicit Fenwick(int n) : n(n), tree(n + 1, 0) {}
static Fenwick build(const std::vector<long long>& a) { // a is 0-based, O(n)
Fenwick fw(static_cast<int>(a.size()));
for (int i = 1; i <= fw.n; ++i) {
fw.tree[i] += a[i - 1];
int j = i + (i & -i);
if (j <= fw.n) fw.tree[j] += fw.tree[i];
}
return fw;
}
std::vector<int> add(int i, long long delta) {
std::vector<int> touched;
for (; i <= n; i += i & -i) {
tree[i] += delta;
touched.push_back(i);
}
return touched;
}
long long prefix(int i) const {
long long s = 0;
for (; i > 0; i -= i & -i) s += tree[i];
return s;
}
long long rangeSum(int l, int r) const { return prefix(r) - prefix(l - 1); }
int lowerBound(long long k) const { // smallest i with prefix(i) >= k; n + 1 if none
int pos = 0, step = 1;
while (step <= n) step <<= 1;
for (; step > 0; step >>= 1) {
int nxt = pos + step;
if (nxt <= n && tree[nxt] < k) {
pos = nxt;
k -= tree[nxt];
}
}
return pos + 1;
}
long long cell(int i) const { return tree[i]; }
};
std::int64_t seed = 42;
std::int64_t next() {
seed = seed * 48271 % 2147483647LL;
return seed;
}
int main() {
std::vector<long long> a = {5, 3, 7, 9, 6, 4, 1, 2, 8, 2, 5, 3, 7, 1, 4, 6};
Fenwick fw = Fenwick::build(a);
std::vector<long long> expectTree = {5, 8, 7, 24, 6, 10, 1, 37, 8, 10, 5, 18, 7, 8, 4, 73};
for (int i = 1; i <= 16; ++i) assert(fw.cell(i) == expectTree[i - 1]);
assert(fw.prefix(13) == 62 && fw.rangeSum(5, 8) == 13);
assert((fw.add(5, 3) == std::vector<int>{5, 6, 8, 16}));
assert(fw.prefix(13) == 65 && fw.lowerBound(40) == 8);
assert(fw.lowerBound(1) == 1 && fw.lowerBound(76) == 16 && fw.lowerBound(77) == 17);
const int n = 37;
std::vector<long long> brute(n);
for (auto& x : brute) x = next() % 100;
Fenwick rf = Fenwick::build(brute);
for (int it = 0; it < 2000; ++it) {
if (next() % 2 == 0) {
int p = static_cast<int>(next() % n);
long long d = next() % 100;
rf.add(p + 1, d);
brute[p] += d;
} else {
int l = static_cast<int>(next() % n), r = static_cast<int>(next() % n);
if (l > r) std::swap(l, r);
long long expect = 0, total = 0;
for (int i = l; i <= r; ++i) expect += brute[i];
assert(rf.rangeSum(l + 1, r + 1) == expect);
for (long long v : brute) total += v;
long long k = next() % (total + 1) + 1, prefix = 0;
int want = n + 1;
for (int i = 0; i < n; ++i) {
prefix += brute[i];
if (prefix >= k) { want = i + 1; break; }
}
assert(rf.lowerBound(k) == want);
}
}
std::cout << "fenwick ok\n";
return 0;
}
class Fenwick {
readonly n: number;
readonly tree: number[];
constructor(n: number) {
this.n = n;
this.tree = new Array<number>(n + 1).fill(0);
}
static build(a: number[]): Fenwick {
// a is 0-based, O(n)
const fw = new Fenwick(a.length);
for (let i = 1; i <= fw.n; i++) {
fw.tree[i] += a[i - 1];
const j = i + (i & -i);
if (j <= fw.n) fw.tree[j] += fw.tree[i];
}
return fw;
}
add(i: number, delta: number): number[] {
const touched: number[] = [];
for (; i <= this.n; i += i & -i) {
this.tree[i] += delta;
touched.push(i);
}
return touched;
}
prefix(i: number): number {
let s = 0;
for (; i > 0; i -= i & -i) s += this.tree[i];
return s;
}
rangeSum(l: number, r: number): number {
return this.prefix(r) - this.prefix(l - 1);
}
lowerBound(k: number): number {
// smallest i with prefix(i) >= k; n + 1 if none
let pos = 0;
let step = 1;
while (step <= this.n) step <<= 1;
for (; step > 0; step >>= 1) {
const nxt = pos + step;
if (nxt <= this.n && this.tree[nxt] < k) {
pos = nxt;
k -= this.tree[nxt];
}
}
return pos + 1;
}
}
let seed = 42;
function next(): number {
seed = (seed * 48271) % 2147483647;
return seed;
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error(msg);
}
const a = [5, 3, 7, 9, 6, 4, 1, 2, 8, 2, 5, 3, 7, 1, 4, 6];
const fw = Fenwick.build(a);
check(fw.tree.slice(1).join() === [5, 8, 7, 24, 6, 10, 1, 37, 8, 10, 5, 18, 7, 8, 4, 73].join(), "build");
check(fw.prefix(13) === 62 && fw.rangeSum(5, 8) === 13, "prefix");
check(fw.add(5, 3).join() === "5,6,8,16", "touched");
check(fw.prefix(13) === 65 && fw.lowerBound(40) === 8, "after");
check(fw.lowerBound(1) === 1 && fw.lowerBound(76) === 16 && fw.lowerBound(77) === 17, "bounds");
const n = 37;
const brute: number[] = [];
for (let i = 0; i < n; i++) brute.push(next() % 100);
const rf = Fenwick.build(brute);
for (let it = 0; it < 2000; it++) {
if (next() % 2 === 0) {
const p = next() % n;
const d = next() % 100;
rf.add(p + 1, d);
brute[p] += d;
} else {
let l = next() % n;
let r = next() % n;
if (l > r) [l, r] = [r, l];
let expect = 0;
for (let i = l; i <= r; i++) expect += brute[i];
check(rf.rangeSum(l + 1, r + 1) === expect, "range");
const total = brute.reduce((x, y) => x + y, 0);
const k = (next() % (total + 1)) + 1;
let prefix = 0;
let want = n + 1;
for (let i = 0; i < n; i++) {
prefix += brute[i];
if (prefix >= k) {
want = i + 1;
break;
}
}
check(rf.lowerBound(k) === want, "lower bound");
}
}
console.log("fenwick ok");
Range update + range query with two BITs
The derivation above, in code. Tests replay add(2, 6, +2) on [5, 3, 7, 9, 6, 4, 1, 2] and then 2,000 random range adds and range sums against brute force.
class RangeFenwick:
"""Range add and range sum, 1-based, via prefix(i) = i*B1(i) - B2(i)."""
def __init__(self, a: list[int]) -> None:
self.n = len(a)
self.b1 = [0] * (self.n + 2)
self.b2 = [0] * (self.n + 2)
prev = 0
for i, v in enumerate(a, 1): # load the difference array
self._point(i, v - prev)
prev = v
def _add(self, tree: list[int], i: int, delta: int) -> None:
while i <= self.n:
tree[i] += delta
i += i & -i
def _sum(self, tree: list[int], i: int) -> int:
s = 0
while i > 0:
s += tree[i]
i -= i & -i
return s
def _point(self, i: int, d: int) -> None: # D[i] += d
self._add(self.b1, i, d)
self._add(self.b2, i, d * (i - 1))
def range_add(self, l: int, r: int, x: int) -> None:
self._point(l, x)
if r + 1 <= self.n:
self._point(r + 1, -x)
def prefix(self, i: int) -> int:
return i * self._sum(self.b1, i) - self._sum(self.b2, i)
def range_sum(self, l: int, r: int) -> int:
return self.prefix(r) - self.prefix(l - 1)
if __name__ == "__main__":
rf = RangeFenwick([5, 3, 7, 9, 6, 4, 1, 2])
rf.range_add(2, 6, 2)
assert rf.range_sum(1, 8) == 47 and rf.range_sum(1, 4) == 30 and rf.range_sum(4, 5) == 19
seed, n = 7, 37
def rnd() -> int:
global seed
seed = seed * 48271 % 2147483647
return seed
brute = [rnd() % 100 for _ in range(n)]
rf = RangeFenwick(brute)
for _ in range(2000):
op, l, r = rnd() % 2, rnd() % n, rnd() % n
l, r = min(l, r), max(l, r)
if op == 0:
x = rnd() % 50
rf.range_add(l + 1, r + 1, x)
for i in range(l, r + 1):
brute[i] += x
else:
assert rf.range_sum(l + 1, r + 1) == sum(brute[l:r + 1])
print("range fenwick ok")
public class RangeFenwick {
private final int n;
private final long[] b1, b2;
RangeFenwick(long[] a) {
n = a.length;
b1 = new long[n + 2];
b2 = new long[n + 2];
long prev = 0;
for (int i = 1; i <= n; i++) { // load the difference array
point(i, a[i - 1] - prev);
prev = a[i - 1];
}
}
private void add(long[] tree, int i, long delta) {
for (; i <= n; i += i & -i) tree[i] += delta;
}
private long sum(long[] tree, int i) {
long s = 0;
for (; i > 0; i -= i & -i) s += tree[i];
return s;
}
private void point(int i, long d) { // D[i] += d
add(b1, i, d);
add(b2, i, d * (i - 1));
}
void rangeAdd(int l, int r, long x) {
point(l, x);
if (r + 1 <= n) point(r + 1, -x);
}
long prefix(int i) {
return i * sum(b1, i) - sum(b2, i);
}
long rangeSum(int l, int r) {
return prefix(r) - prefix(l - 1);
}
static long seed = 7;
static long next() {
seed = seed * 48271 % 2147483647L;
return seed;
}
private static void check(boolean cond, String msg) {
if (!cond) throw new AssertionError(msg);
}
public static void main(String[] args) {
RangeFenwick rf = new RangeFenwick(new long[] {5, 3, 7, 9, 6, 4, 1, 2});
rf.rangeAdd(2, 6, 2);
check(rf.rangeSum(1, 8) == 47 && rf.rangeSum(1, 4) == 30 && rf.rangeSum(4, 5) == 19, "trace");
int n = 37;
long[] brute = new long[n];
for (int i = 0; i < n; i++) brute[i] = next() % 100;
rf = new RangeFenwick(brute.clone());
for (int it = 0; it < 2000; it++) {
long op = next() % 2;
int l = (int) (next() % n), r = (int) (next() % n);
if (l > r) { int tmp = l; l = r; r = tmp; }
if (op == 0) {
long x = next() % 50;
rf.rangeAdd(l + 1, r + 1, x);
for (int i = l; i <= r; i++) brute[i] += x;
} else {
long expect = 0;
for (int i = l; i <= r; i++) expect += brute[i];
check(rf.rangeSum(l + 1, r + 1) == expect, "random");
}
}
System.out.println("range fenwick ok");
}
}
#include <cassert>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
class RangeFenwick {
int n;
std::vector<long long> b1, b2;
void add(std::vector<long long>& tree, int i, long long delta) {
for (; i <= n; i += i & -i) tree[i] += delta;
}
long long sum(const std::vector<long long>& tree, int i) const {
long long s = 0;
for (; i > 0; i -= i & -i) s += tree[i];
return s;
}
void point(int i, long long d) { // D[i] += d
add(b1, i, d);
add(b2, i, d * (i - 1));
}
public:
explicit RangeFenwick(const std::vector<long long>& a)
: n(static_cast<int>(a.size())), b1(a.size() + 2), b2(a.size() + 2) {
long long prev = 0;
for (int i = 1; i <= n; ++i) { // load the difference array
point(i, a[i - 1] - prev);
prev = a[i - 1];
}
}
void rangeAdd(int l, int r, long long x) {
point(l, x);
if (r + 1 <= n) point(r + 1, -x);
}
long long prefix(int i) const { return i * sum(b1, i) - sum(b2, i); }
long long rangeSum(int l, int r) const { return prefix(r) - prefix(l - 1); }
};
std::int64_t seed = 7;
std::int64_t next() {
seed = seed * 48271 % 2147483647LL;
return seed;
}
int main() {
RangeFenwick rf({5, 3, 7, 9, 6, 4, 1, 2});
rf.rangeAdd(2, 6, 2);
assert(rf.rangeSum(1, 8) == 47 && rf.rangeSum(1, 4) == 30 && rf.rangeSum(4, 5) == 19);
const int n = 37;
std::vector<long long> brute(n);
for (auto& x : brute) x = next() % 100;
RangeFenwick rr(brute);
for (int it = 0; it < 2000; ++it) {
auto op = next() % 2;
int l = static_cast<int>(next() % n), r = static_cast<int>(next() % n);
if (l > r) std::swap(l, r);
if (op == 0) {
long long x = next() % 50;
rr.rangeAdd(l + 1, r + 1, x);
for (int i = l; i <= r; ++i) brute[i] += x;
} else {
long long expect = 0;
for (int i = l; i <= r; ++i) expect += brute[i];
assert(rr.rangeSum(l + 1, r + 1) == expect);
}
}
std::cout << "range fenwick ok\n";
return 0;
}
class RangeFenwick {
private n: number;
private b1: number[];
private b2: number[];
constructor(a: number[]) {
this.n = a.length;
this.b1 = new Array<number>(this.n + 2).fill(0);
this.b2 = new Array<number>(this.n + 2).fill(0);
let prev = 0;
a.forEach((v, idx) => {
this.point(idx + 1, v - prev); // load the difference array
prev = v;
});
}
private add(tree: number[], i: number, delta: number): void {
for (; i <= this.n; i += i & -i) tree[i] += delta;
}
private sum(tree: number[], i: number): number {
let s = 0;
for (; i > 0; i -= i & -i) s += tree[i];
return s;
}
private point(i: number, d: number): void {
this.add(this.b1, i, d);
this.add(this.b2, i, d * (i - 1));
}
rangeAdd(l: number, r: number, x: number): void {
this.point(l, x);
if (r + 1 <= this.n) this.point(r + 1, -x);
}
prefix(i: number): number {
return i * this.sum(this.b1, i) - this.sum(this.b2, i);
}
rangeSum(l: number, r: number): number {
return this.prefix(r) - this.prefix(l - 1);
}
}
let seed = 7;
function next(): number {
seed = (seed * 48271) % 2147483647;
return seed;
}
function check(cond: boolean, msg: string): void {
if (!cond) throw new Error(msg);
}
const rf = new RangeFenwick([5, 3, 7, 9, 6, 4, 1, 2]);
rf.rangeAdd(2, 6, 2);
check(rf.rangeSum(1, 8) === 47 && rf.rangeSum(1, 4) === 30 && rf.rangeSum(4, 5) === 19, "trace");
const n = 37;
const brute: number[] = [];
for (let i = 0; i < n; i++) brute.push(next() % 100);
const rr = new RangeFenwick(brute.slice());
for (let it = 0; it < 2000; it++) {
const op = next() % 2;
let l = next() % n;
let r = next() % n;
if (l > r) [l, r] = [r, l];
if (op === 0) {
const x = next() % 50;
rr.rangeAdd(l + 1, r + 1, x);
for (let i = l; i <= r; i++) brute[i] += x;
} else {
let expect = 0;
for (let i = l; i <= r; i++) expect += brute[i];
check(rr.rangeSum(l + 1, r + 1) === expect, "random");
}
}
console.log("range fenwick ok");
Variant: range update, point query
class DiffFenwick:
def __init__(self, n: int) -> None:
self.n = n
self.t = [0] * (n + 1)
def _add(self, i: int, d: int) -> None:
while i <= self.n:
self.t[i] += d
i += i & -i
def range_add(self, l: int, r: int, x: int) -> None: # 1-based, inclusive
self._add(l, x)
if r + 1 <= self.n:
self._add(r + 1, -x)
def get(self, i: int) -> int: # a[i] = prefix of differences
s = 0
while i > 0:
s += self.t[i]
i -= i & -i
return s
df = DiffFenwick(8)
df.range_add(2, 6, 2)
df.range_add(5, 8, 10)
assert [df.get(i) for i in range(1, 9)] == [0, 2, 2, 2, 12, 12, 10, 10]
print("range update point query ok")
Variant: inversion counting with coordinate compression
from bisect import bisect_left
def count_inversions(a: list[int]) -> int:
ranks = sorted(set(a))
m = len(ranks)
tree = [0] * (m + 1)
inversions = 0
for seen, x in enumerate(a):
r = bisect_left(ranks, x) + 1 # 1-based rank
s, i = 0, r # s = earlier elements <= x
while i > 0:
s += tree[i]
i -= i & -i
inversions += seen - s # earlier elements > x
i = r
while i <= m:
tree[i] += 1
i += i & -i
return inversions
def brute(a: list[int]) -> int:
return sum(a[i] > a[j] for i in range(len(a)) for j in range(i + 1, len(a)))
assert count_inversions([100, 7, 100, 3, 50]) == 6
assert count_inversions([8, 4, 2, 1]) == 6 and count_inversions([3, 1, 2]) == 2
assert count_inversions([2, 4, 1, 3, 5]) == 3 and count_inversions([]) == 0
data = [((i * 7919) % 101) - 50 for i in range(200)]
assert count_inversions(data) == brute(data)
print("inversions ok")
Variant: 2D Fenwick tree
class Fenwick2D:
def __init__(self, rows: int, cols: int) -> None:
self.r, self.c = rows, cols
self.t = [[0] * (cols + 1) for _ in range(rows + 1)]
def add(self, x: int, y: int, d: int) -> None: # 1-based cell
i = x
while i <= self.r:
j = y
row = self.t[i]
while j <= self.c:
row[j] += d
j += j & -j
i += i & -i
def prefix(self, x: int, y: int) -> int: # sum of [1..x] x [1..y]
s, i = 0, x
while i > 0:
j = y
row = self.t[i]
while j > 0:
s += row[j]
j -= j & -j
i -= i & -i
return s
def rect(self, x1: int, y1: int, x2: int, y2: int) -> int:
return (self.prefix(x2, y2) - self.prefix(x1 - 1, y2)
- self.prefix(x2, y1 - 1) + self.prefix(x1 - 1, y1 - 1))
grid = [[(r * 3 + c * 5) % 7 for c in range(6)] for r in range(5)]
f2 = Fenwick2D(5, 6)
for r in range(5):
for c in range(6):
f2.add(r + 1, c + 1, grid[r][c])
f2.add(3, 4, 10)
grid[2][3] += 10
for x1 in range(1, 6):
for x2 in range(x1, 6):
for y1 in range(1, 7):
for y2 in range(y1, 7):
expect = sum(grid[r][c] for r in range(x1 - 1, x2) for c in range(y1 - 1, y2))
assert f2.rect(x1, y1, x2, y2) == expect
print("2d fenwick ok")
Variant: an order-statistic multiset
A count BIT over a fixed universe of values gives insert, erase, rank and k-th smallest, all in — a lightweight replacement for a balanced BST when values are bounded or known in advance (compress them).
class OrderedMultiset:
def __init__(self, universe: int) -> None: # values in [0, universe)
self.n = universe
self.t = [0] * (universe + 1)
self.size = 0
self.top = 1 << universe.bit_length()
def _add(self, i: int, d: int) -> None:
while i <= self.n:
self.t[i] += d
i += i & -i
def insert(self, v: int) -> None:
self._add(v + 1, 1)
self.size += 1
def erase(self, v: int) -> None: # caller ensures v is present
self._add(v + 1, -1)
self.size -= 1
def rank(self, v: int) -> int: # how many elements < v
s, i = 0, v
while i > 0:
s += self.t[i]
i -= i & -i
return s
def kth(self, k: int) -> int: # 1-based k-th smallest
pos, step = 0, self.top
while step:
nxt = pos + step
if nxt <= self.n and self.t[nxt] < k:
pos = nxt
k -= self.t[nxt]
step >>= 1
return pos # index pos + 1 holds value pos
ms = OrderedMultiset(100)
for v in [42, 7, 42, 99, 0, 63]:
ms.insert(v)
assert [ms.kth(k) for k in range(1, 7)] == [0, 7, 42, 42, 63, 99]
assert ms.rank(42) == 2 and ms.rank(43) == 4
ms.erase(42)
assert [ms.kth(k) for k in range(1, 6)] == [0, 7, 42, 63, 99]
print("order statistics ok")
Real-world uses
- Adaptive arithmetic coding and range coding. Fenwick's motivating application: an adaptive entropy coder needs, for every symbol, the cumulative frequency of all smaller symbols (to compute the coding interval) and then increments that symbol's count. With a BIT both are for alphabet size , instead of for a plain cumulative table. Compression libraries with large adaptive alphabets use this or close relatives; many small-alphabet coders still use simple linear tables because is tiny.
- Rank and percentile queries on changing data. "What rank is this score?" on a leaderboard with bounded scores, "how many requests took less than 200 ms in this window?" over bucketed latencies, "what is the 99th percentile?" via
lower_boundon a count BIT over histogram buckets. The disk-or-network equivalents are B-trees with subtree counts and Redis sorted sets, which keep span counts in their skip list to answerZRANKin (see Redis internals). - Weighted sampling with changing weights. Sampling an index with probability proportional to a weight, where weights change: draw uniformly in and descend with
lower_bound(u + 1)over integer weights. The same job as the sum tree in prioritized experience replay, in less memory. See probability for engineers. - Order books and cumulative depth. Price levels on an exchange form a bounded integer grid; "total volume at prices up to p" with constant updates is exactly a dynamic prefix sum. Whether a given matching engine uses a BIT, a segment tree or a tree map is an implementation detail most do not publish, so treat this as a natural fit rather than a documented fact.
- Statistics and ranking metrics. Kendall's tau rank correlation counts discordant pairs — inversions after sorting by one variable — and is computed in by merge-sort or BIT-based inversion counting (Knight's 1966 algorithm uses merge sort; BIT versions are a common alternative).
- Computational geometry sweeps. Counting points dominated by each point, counting intersecting horizontal/vertical segments, and offline rectangle queries reduce to a sweep line with a BIT over compressed coordinates. See spatial indexing.
Pitfalls & edge cases
- Zero-based indexing.
i & -iis 0 fori = 0, soadd(0, d)loops forever andprefix(0)is fine only because it exits immediately. Keep the BIT 1-based internally and convert at the boundary (add(i + 1, d)). - Size. The array has cells; the update loop must use
i <= n, noti < n. The two-BIT version callspoint(r + 1, …), which is a no-op when if guarded, or needs an array of size . - Range sum with l = 1.
prefix(l - 1) = prefix(0) = 0, which works automatically. Do not special-case it. - Overflow. Sums of values up to need 64-bit; the two-BIT formula multiplies by and by , so intermediate values can reach — check that fits.
- Negative values and lower_bound. Binary lifting finds the first prefix only if prefix sums are non-decreasing, i.e. all values non-negative. With negatives it returns a wrong index silently.
- Assignment instead of add. A BIT supports
add. To seta[i] = v, keep the raw array and calladd(i, v - a[i]). - Compression with duplicates. Use
bisect_lefton the sorted distinct values so equal values get equal ranks; then decide strict versus non-strict comparisons explicitly ("greater than" queries subtractprefix(rank), "greater or equal" subtractprefix(rank - 1)). - Min/max BIT. A "prefix minimum BIT" works only if updates never increase a value (or only ever decrease the minimum). Arbitrary updates require a segment tree. Range (non-prefix) min is not available at all from the standard BIT.
- JavaScript numbers. Sums above lose precision silently; use
BigIntor split into high/low parts if they can get that large. - Building with repeated adds on huge inputs. is usually fine, but the linear build is just as short — use it.
Variations
- Segment tree: everything a BIT does plus non-invertible operations, range assignment, custom merges, descents with arbitrary predicates and persistence, at 2–4× the memory and more code. Segment trees in depth.
- Range update + range query in 2D: four 2D BITs, using the same derivation per dimension (the prefix of a 2D difference array expands into four terms). Heavy but standard.
- Fenwick tree of sorted vectors / of BITs (offline): for 2D counting with large coordinates, allocate per-node inner structures only for the coordinates that will be queried.
- XOR and other group operations: replace
+/-with any abelian group operation and its inverse. XOR is its own inverse, so range XOR isprefix(r) ^ prefix(l - 1). - Prefix max/min with monotone updates: if updates only increase values (for max),
tree[i] = max(tree[i], v)along the update chain and a prefix-max query along the query chain work. This is the standard trick for longest-increasing-subsequence DP in with a BIT over values. - Fenwick tree with range minimum queries: there are published constructions using two BITs to answer arbitrary range minima ("Efficient Range Minimum Queries using Binary Indexed Trees", Dima and Ceterchi, Olympiads in Informatics 2015), but they are more complex than a segment tree and rarely worth it.
- Sparse table and sqrt decomposition: static or semi-static alternatives, see the sparse tables lesson.
Fenwick tree vs segment tree
| Question | Fenwick tree | Segment tree |
|---|---|---|
| Memory for elements | (iterative) to (recursive), double with lazy | |
| Code size (sum + point update) | ~10 lines | ~20 (iterative) to ~40 (recursive) |
| Constant factor | Smallest | Iterative close; recursive 2–4× slower |
| Range sum, point update | Yes | Yes |
| Range min/max/gcd with point updates | No (prefix only, monotone updates) | Yes |
| Range add + range sum | Yes (two BITs) | Yes (lazy) |
| Range assign | No | Yes (lazy) |
| Custom merges (max subarray, matrices) | No | Yes |
| k-th element / first prefix ≥ k | Yes (binary lifting, non-negative) | Yes (descent, any monotone predicate) |
| Persistence | Awkward | Natural (path copying) |
| 2D | Easy (nested loops) | Possible, heavier |
The rule of thumb: if the operation has an inverse and the updates are additive, use a Fenwick tree; otherwise use a segment tree.
Practice ladder
Each problem is described in my own words; follow the link for the formal statement.
1. Range Sum Query – Mutable (LeetCode 307) — Point assignment and range sum. Teaches converting "set" into "add the difference".
Hint
Keep a copy of the array. update(i, v) becomes add(i + 1, v - a[i]); then store a[i] = v.
2. Dynamic Range Sum Queries (CSES 1648) — The same at . Teaches the linear build and 64-bit sums.
Hint
Build in , use long long, read input fast.
3. Range Xor Queries (CSES 1650) — Static range XOR. Teaches that XOR is its own inverse (a static prefix XOR suffices here; a BIT with ^ handles the dynamic version).
Hint
xor(l, r) = P[r] ^ P[l - 1]. For updates, the BIT uses ^= in both loops.
4. Range Update Queries (CSES 1651) — Range add, point read. Teaches the difference-array BIT.
Hint
add(l, x), add(r + 1, -x); the value at is a[k] + prefix(k).
5. Forest Queries II (CSES 1739) — Toggle trees in a grid and count trees in rectangles. Teaches the 2D BIT.
Hint
2D BIT over 0/1 cells; a toggle is add(±1). Rectangle by inclusion–exclusion over four prefixes.
6. Count of Smaller Numbers After Self (LeetCode 315) — For each element, count smaller elements to its right. Teaches the right-to-left sweep over compressed values.
Hint
Sweep from the right; before inserting x, the answer is prefix(rank(x) - 1) (strictly smaller).
Solution
from bisect import bisect_left
def count_smaller(nums: list[int]) -> list[int]:
vals = sorted(set(nums))
m = len(vals)
tree = [0] * (m + 1)
out = [0] * len(nums)
for idx in range(len(nums) - 1, -1, -1):
r = bisect_left(vals, nums[idx]) + 1
s, i = 0, r - 1 # strictly smaller: ranks 1..r-1
while i > 0:
s += tree[i]
i -= i & -i
out[idx] = s
i = r
while i <= m:
tree[i] += 1
i += i & -i
return out
assert count_smaller([5, 2, 6, 1]) == [2, 1, 1, 0]
assert count_smaller([-1, -1]) == [0, 0]
assert count_smaller([2, 0, 1]) == [2, 0, 0]
print("315 ok")
.
7. Inversion Count (SPOJ INVCNT) — Count inversions in arrays up to elements. The count_inversions variant above; compare with merge sort.
Hint
Compress, sweep left to right, add seen - prefix(rank). Use 64-bit counts: can exceed .
8. Salary Queries (CSES 1144) — Change salaries and count employees with salary in . Teaches offline coordinate compression over all values that will ever appear.
Hint
Read all queries first, compress every initial salary, every new salary and every query bound together. Then a count BIT over compressed values: change = -1 at old, +1 at new; query = range count.
9. List Removals (CSES 1749) — Remove the element at a given position of the current list, repeatedly. Teaches k-th by binary lifting.
Hint
BIT of ones. Position in the current list is lower_bound(p); print it and add(idx, -1).
10. Josephus Problem II (CSES 2163) — Children in a circle; every -th is removed; print the order. Teaches modular position arithmetic on top of the k-th query.
Hint
Keep the current position as a rank among remaining children: pos = (pos + k) % remaining, then remove the (pos + 1)-th one with lower_bound.
Solution
def josephus(n: int, k: int) -> list[int]:
tree = [0] * (n + 1)
for i in range(1, n + 1): # linear build of all ones
tree[i] += 1
j = i + (i & -i)
if j <= n:
tree[j] += tree[i]
top = 1 << n.bit_length()
def kth(r: int) -> int:
pos, step = 0, top
while step:
nxt = pos + step
if nxt <= n and tree[nxt] < r:
pos = nxt
r -= tree[nxt]
step >>= 1
return pos + 1
order, pos = [], 0
for remaining in range(n, 0, -1):
pos = (pos + k) % remaining
child = kth(pos + 1)
order.append(child)
i = child
while i <= n:
tree[i] -= 1
i += i & -i
return order
assert josephus(7, 2) == [3, 6, 2, 7, 5, 1, 4]
assert josephus(5, 0) == [1, 2, 3, 4, 5]
assert josephus(1, 10) == [1]
print("2163 ok")
.
11. Multiset (Codeforces 1354D) — A multiset with insertions and "remove the k-th smallest", under a tight memory limit. Teaches the count BIT as a compact order-statistic tree.
Hint
Values are bounded by , so a count BIT over values works without compression. Removal of the k-th is lower_bound(k) then add(-1). Output any remaining element at the end.
12. Distinct Values Queries (CSES 1734) — Count distinct values in many subarrays. Teaches the offline "last occurrence" trick.
Hint
Sort queries by right end. Sweep left to right; for a[r], add(last[a[r]], -1) if it occurred before, then add(r, +1), last[a[r]] = r. A query is range_sum(l, r): only the last occurrence of each value up to is marked.
Solution
def distinct_queries(a: list[int], queries: list[tuple[int, int]]) -> list[int]:
n = len(a)
tree = [0] * (n + 1)
def add(i: int, d: int) -> None:
while i <= n:
tree[i] += d
i += i & -i
def prefix(i: int) -> int:
s = 0
while i > 0:
s += tree[i]
i -= i & -i
return s
order = sorted(range(len(queries)), key=lambda q: queries[q][1])
last: dict[int, int] = {}
ans = [0] * len(queries)
r = 0
for qi in order:
l, qr = queries[qi] # 1-based inclusive
while r < qr:
r += 1
v = a[r - 1]
if v in last:
add(last[v], -1)
add(r, 1)
last[v] = r
ans[qi] = prefix(qr) - prefix(l - 1)
return ans
arr = [3, 2, 3, 1, 2]
qs = [(1, 3), (3, 4), (1, 5), (2, 2)]
assert distinct_queries(arr, qs) == [2, 2, 3, 1]
print("1734 ok")
.
13. Create Sorted Array through Instructions (LeetCode 1649) — Insert numbers one by one; each costs the smaller of "strictly less" and "strictly greater" counts already present. Teaches both-sided rank queries.
Hint
Values are bounded (), so a count BIT over values. Less = prefix(v - 1); greater = inserted - prefix(v). Take the minimum, modulo .
14. Enemy is weak (Codeforces 61E) — Count triples with (distinct values). Teaches combining two sweeps: for each middle element, (greater on the left) × (smaller on the right).
Hint
One left-to-right BIT sweep gives greater_left[j]; one right-to-left sweep gives smaller_right[j]. Sum their products in 64-bit.
15. Count Good Triplets in an Array (LeetCode 2179) — Two permutations; count value triples appearing in the same relative order in both. Teaches remapping one permutation through the other, then the 61E-style two-sweep count.
Hint
Replace each value of nums1 by its position in nums2. Now count increasing triples with : for each , (smaller on the left) × (larger on the right).
Common mistakes & interview follow-ups
"Explain i & -i." Two's complement: , which flips every bit above the lowest set bit and keeps that bit and the zeros below it. AND leaves only the lowest set bit.
"Why is it called a tree when it is an array?" The cells form two implicit trees: the update tree (, each block nested in its parent's) and the query tree (, each step jumping to the block on the left). Neither is stored; both are computed by bit arithmetic.
"Can you do range minimum with a Fenwick tree?" Not for arbitrary ranges with arbitrary updates: min has no inverse, so prefix(r) - prefix(l - 1) has no analogue. Prefix minimum with only-decreasing updates works. Otherwise use a segment tree or a sparse table.
"Range add and range sum?" Two BITs: , with over and over . Be ready to derive it from — interviewers prefer the derivation to the formula.
"Find the median of a stream with bounded values?" Count BIT over values; the median is lower_bound((count + 1) // 2). per insert and per query. With unbounded values, compress offline or use two heaps (see heaps).
"Values are up to ." Coordinate-compress all values that will ever be inserted or queried (offline), or switch to a dynamic segment tree or a balanced BST (online).
"What if the array grows?" Appending to a BIT is possible: the new cell covers , computable from prefix sums in . Many implementations simply preallocate the maximum size.
Common mistakes interviewers watch for: 0-based loops that never terminate; < instead of <= in the update loop; forgetting that "set" must become "add the difference"; lower_bound on data with negative values; 32-bit overflow in inversion counts.
Quick quiz
1. Which cells does prefix(22) read, and which cells does add(22, d) modify, with ?
Answer
. Prefix strips low bits: 22, 20, 16 (three cells, popcount 3). Update adds low bits: 22, 24, 32 (then 64 > 32 stops). Check with the zero-bit rule: has zero bits at positions 1 and 3 (and 5 and beyond); the cells are , , .
2. What block does tree[12] cover, and why?
Answer
, lowbit 4, so it covers .
3. In the two-BIT range update, why is updated with at and at ?
Answer
stores . The range add changes by and by , so changes by at and at .
4. Why must values be non-negative for the binary-lifting lower bound?
Answer
The descent assumes prefix sums are non-decreasing so that "the first index where the prefix reaches k" is found by greedily accepting blocks whose sum is below the remaining k. With negative values a later prefix can drop below k again, and greedy acceptance can skip over the true first index.
5. You need range minimum queries with point updates. Fenwick or segment tree?
Answer
Segment tree. Min is not invertible, so a range cannot be obtained as the difference of two prefixes. A Fenwick tree only gives prefix minima, and only under updates that never increase a value.
Further reading / sources
- Peter M. Fenwick, "A New Data Structure for Cumulative Frequency Tables", Software: Practice and Experience 24(3):327–336, 1994.
- Boris Ryabko, "A fast on-line adaptive code", IEEE Transactions on Information Theory 38(4), 1992 (building on his 1989 work) — an earlier form of the same idea.
- cp-algorithms: Fenwick Tree — 0-based and 1-based variants, range updates, 2D.
- Antti Laaksonen, Competitive Programmer's Handbook, chapter 9 "Range queries", section on binary indexed trees.
- Topcoder tutorial "Binary Indexed Trees" by boba5551 — the classic introduction, including the k-th element search.
- Mircea Dima and Rodica Ceterchi, "Efficient Range Minimum Queries using Binary Indexed Trees", Olympiads in Informatics 9, 2015.
- Thomas H. Cormen et al., Introduction to Algorithms, 3rd ed., problem 2-4 "Inversions" (the merge-sort counting method used as the comparison rung).
Previous lesson: Segment Trees in Depth · Next lesson: Sparse Tables, Sqrt Decomposition & Mo's Algorithm
Related: Module 3 overview · Prefix Sums & Difference Arrays · Bit Manipulation · Advanced Data Structures · Trees overview · Tries in Depth · Capstone: A Range-Query Engine · Sorting & Searching · Course home