Skip to main content
Definition Website Computer and Technology

Fenwick Tree

Subject: Computer and Technology noun /ˈfɛn.wɪk triː/ 1 definition

  1. Definition (noun)

    Entry #279 · Updated

    A 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 i aggregates a contiguous subrange whose length equals the least significant set bit of i (i & -i). Both prefix sum queries and point updates step across these bit-aligned partial aggregates using bitwise arithmetic, completing in O(log n) time and O(n) space with low constant-factor overhead. While arbitrary interval sums [l, r] follow from prefix(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 in O(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 (at l and r + 1), while reading an element at index k reduces 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 & -i traversal pattern across two or more array axes (such as an M x N grid), supporting point updates and submatrix prefix queries in O(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_t Fenwick Tree array of 257 elements. When encoding byte 0x41 (1-based index 66), the compressor increments slots 66, 68, 72, 80, 96, 128, and 256 via i += i & -i, and resolves cumulative symbol intervals in at most 8 i -= i & -i lookups rather than scanning up to 256 frequency bins.