Fenwick Tree

Fenwick tree (also known as a Binary Indexed Tree, or BIT) is an implicit, space-optimal array data structure within computation and algorithms that maintains dynamic cumulative frequencies (prefix sums) of an array A[1..n] and executes both prefix queries and point updates in worst-case O(log n) time while using zero auxiliary memory beyond the n-element array itself. Invented in 1989 by Boris Ryabko and independently discovered and popularized in 1994 by Peter M. Fenwick in Software: Practice and Experience to accelerate dynamic symbol probability tables for arithmetic data compression, the Fenwick tree bridges the gap between a raw array (O(1) update, O(n) prefix sum) and a static prefix-sum array (O(n) update, O(1) prefix sum).

By indexing the array from 1 to n and decomposing every integer index i according to the least significant set bit in its binary representation, a Fenwick tree navigates an implicit binomial-like tree hierarchy using a single CPU two's-complement bitwise instruction (i & (−i)) per tree step. Within computational complexity theory and algorithm engineering, a Fenwick tree requires half to one-quarter the memory of a segment tree or balanced AVL tree and achieves high L1/L2 cache locality for dynamic rank queries, inversion counting, arithmetic coding, and Gillespie stochastic chemical simulation.

Responsibility Length lsb(i) = i & (−i)

Let A[1..n] be a 1-indexed array over an abelian group (G, +, −, 0). For any positive integer i ∈ {1, ..., n}, define lsb(i) (lowbit(i)) as the largest power of two 2^k dividing i—the value of the lowest set bit 1 in i. In two's-complement arithmetic, −i = (~i) + 1 inverts all bits above the lowest set bit k while preserving bit k = 1 and trailing zeros, so bitwise AND isolates 2^k in one instruction:

In the Fenwick array T[1..n], each slot T[i] stores the sum of a block of length lsb(i) ending at i:

Odd indices (i ≡ 1 mod 2) have lsb(i) = 1 (T[i] = A[i]), indices i ≡ 2 (mod 4) store 2-element sums, and powers of two i = 2^k store full prefix sums A[1..2^k].

Prefix Query (Stripping Lowest Bits) and Point Update (Propagating Carries)

Because i = 2^k₁ + ... + 2^k_r (r = popcount(i) ≤ ⌈log₂(n + 1)⌉), the prefix [1, i] partitions into r disjoint blocks. Computing Prefix-Sum(i) = ∑_j=1..i A[j] accumulates T[i] and strips lsb(i) until i = 0:

Conversely, incrementing A[i] by Δ updates all containing ancestors j ≥ i by repeatedly adding lsb(i) until i > n:

Both operations run in at most ⌊log₂ n⌋ + 1 steps, and any range sum over [L, R] is Prefix-Sum(R) − Prefix-Sum(L − 1).

In-Place O(n) Initialization vs. O(n log n) Insertion

Because each node T[i] has a unique parent p(i) = i + (i & (−i)) in the update tree, copying T[i] ← A[i] and propagating each node's total to its immediate parent in a single forward sweep i = 1..n constructs the Fenwick tree in-place in O(n) time using n − 1 additions:

Binary Lifting and Dual Fenwick Trees for Range Updates

When all entries of A[1..n] are non-negative (A[i] ≥ 0), finding the smallest index i with Prefix-Sum(i) ≥ W via binary lifting steps k downward from ⌊log₂ n⌋ to 0 and advances idx ← idx + 2^k (subtracting T[idx + 2^k] from W) whenever T[idx + 2^k] < W, locating the target index in a single O(log n) pass.

To support adding Δ to a subarray A[L..R] while also querying Prefix-Sum(x), define the difference array D[i] = A[i] − A[i − 1]. Expanding the prefix sum algebraically yields:

Maintaining two Fenwick trees—T₁ storing D[j] and T₂ storing (j − 1)·D[j]—evaluates both range additions and range sums in O(log n) time and 2n space.

Peter Fenwick designed the Binary Indexed Tree for adaptive arithmetic coding and the symbol-frequency stage downstream of the Burrows–Wheeler transform (which he integrated into the bzip2 compression ecosystem alongside Huffman coding): adaptive arithmetic coding updates the cumulative frequency interval [C(s), C(s + 1)) of each symbol s after every byte, which a Fenwick tree executes in O(log |Σ|) time. In non-parametric statistics, sweeping an array A[1..n] while inserting each rank into a Fenwick tree counts array inversions (and computes Kendall's τ rank correlation) in O(n log n) time. In chemical kinetics, logarithmic direct Gillespie stochastic simulation algorithms (SSA) store reaction propensities a_μ in a Fenwick tree and use binary lifting to sample the next firing biochemical reaction in O(log M) time.

Why must a Fenwick tree use 1-based indexing instead of 0-based indexing?

In 1-based indexing, every valid index i ∈ {1, ..., n} has a non-zero least significant set bit lsb(i) = i & (−i) ≥ 1, so both i − lsb(i) and i + lsb(i) terminate cleanly. If index 0 were passed into the standard bitwise loops, lsb(0) = 0, causing the update loop i ← i + lsb(i) to stall at i = 0.

Why can a single Fenwick tree not answer arbitrary Range Minimum Queries in O(log n) time?

Range sum queries on [L, R] rely on the additive group inverse (−) so that the prefix [1, L − 1] can be subtracted from [1, R]. The minimum operator min forms a semigroup without an inverse: knowing min(A[1..R]) and min(A[1..L − 1]) does not determine min(A[L..R]) whenever the global minimum lies in [1, L − 1], requiring a segment tree (O(log n)) instead.

1. Ryabko, B. Y. (1989). "A fast on-line code." Soviet Mathematics Doklady, 39(3), 533–537. https://mathscinet.ams.org/mathscinet-getitem?mr=1001696
2. Fenwick, P. M. (1994). "A new data structure for cumulative frequency tables." Software: Practice and Experience, 24(3), 327–336. https://doi.org/10.1002/spe.4380240306
3. Fenwick, P. M. (1996). "Block sorting text compression—final report." The Computer Journal, 39(9), 731–740. https://doi.org/10.1093/comjnl/39.9.731
4. Mishra, P. (2013). "A new algorithm for updating and querying sub-arrays of multidimensional arrays." Journal of Cloud Computing, 2013, 1–8. https://doi.org/10.48550/arXiv.1311.6093
5. Pibiri, G. E., & Venturini, R. (2020). "Practical trade-offs for the prefix-sum problem." Software: Practice and Experience, 51(5), 921–949. https://doi.org/10.1002/spe.2918