Fenwick Tree
Subject: Computer and Technology noun /ˈfɛn.wɪk triː/ 1 definition
- data-structures
- algorithms
- prefix-sums
- computer-science
-
Definition (noun)
Entry #279 · UpdatedA Fenwick Tree (also known as a Binary Indexed Tree, or BIT) is an array-backed data structure that maintains dynamic cumulative frequencies and prefix sums over a mutable sequence of numeric values. Instead of storing explicit tree pointers, each 1-based slot at index
iaggregates a contiguous subrange whose length equals the least significant set bit ofi(i & -i). Both prefix sum queries and point updates step across these bit-aligned partial aggregates using bitwise arithmetic, completing inO(log n)time andO(n)space with low constant-factor overhead. While arbitrary interval sums[l, r]follow fromprefix(r) - prefix(l - 1)for invertible operations such as addition or bitwise XOR, a Fenwick Tree cannot directly support non-invertible range queries like arbitrary range minimum or maximum, where a segment tree is required instead.Common Forms
Point-Update / Range-Query Fenwick Tree: The canonical 1D form backed by a single array of length
n + 1, supporting single-element increments and arbitrary prefix or interval sum queries inO(log n)time.Range-Update / Point-Query Fenwick Tree: Applies a Fenwick Tree over an implicit difference array so adding a delta across
[l, r]requires only two point updates (atlandr + 1), while reading an element at indexkreduces to a prefix sum query.Dual Fenwick Tree (Range-Update / Range-Query): Pairs two coordinated 1D Fenwick Trees over a weighted difference encoding so both interval additions and interval sum queries run in
O(log n)time without allocating a full segment tree.Multi-Dimensional Fenwick Tree: Nests the
i & -itraversal pattern across two or more array axes (such as anM x Ngrid), supporting point updates and submatrix prefix queries inO(log M * log N)time for spatial grids and 2D histograms.
Example
An adaptive arithmetic compressor tracks symbol counts across a 256-byte alphabet in a 1-indexed
uint32_tFenwick Tree array of 257 elements. When encoding byte0x41(1-based index66), the compressor increments slots66,68,72,80,96,128, and256viai += i & -i, and resolves cumulative symbol intervals in at most 8i -= i & -ilookups rather than scanning up to 256 frequency bins.