Fenwick Tree (BIT)
Visualize how a Binary Indexed Tree enables efficient prefix sums and point updates.
Fenwick Tree (BIT)
Concept Overview
A Fenwick Tree, also known as a Binary Indexed Tree (BIT), is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers. Unlike a standard array where prefix sums take O(n) time or updates on a precalculated prefix sum array take O(n) time, a Fenwick Tree achieves both operations in O(log n) time.
Mathematical Definition
The core idea relies on representing the index as a sum of powers of two (similar to binary representation). Each node at index i in the Fenwick tree stores the sum of a specific range of elements from the original array. Specifically, the node at index i is responsible for the range of elements from i - LSB(i) + 1 to i, where LSB(i) is the least significant bit of i.
Let BIT be the Fenwick tree array of size n + 1.
Least Significant Bit (LSB) isolation:
LSB(i) = i & (-i)
Range responsibility for BIT[i]:
BIT[i] = Σk = i - LSB(i) + 1i A[k]
Time Complexity:
- Build: O(n log n) standard, O(n) optimized
- Point Update: O(log n)
- Prefix Query: O(log n)
Space Complexity: O(n)
Key Concepts
- Prefix Sum Query: To calculate the sum of elements from index 1 to x, you initialize a sum variable to 0. Then, iteratively add BIT[x] to the sum and remove the least significant bit from x (x = x - LSB(x)) until x becomes 0.
- Point Update: To add a value v to the element at index x, you iteratively add v to BIT[x] and add the least significant bit to x (x = x + LSB(x)) until x exceeds the size of the array. This correctly updates all nodes that encompass index x.
- 1-Based Indexing: Fenwick Trees conventionally use 1-based indexing because the bitwise operations (specifically isolating the LSB) do not work optimally with an index of 0 (since 0 & -0 is 0, causing an infinite loop).
- Space Efficiency: A Fenwick Tree uses exactly the same amount of space as the original array, making it more space-efficient than a standard Segment Tree which typically requires 4n space.
Historical Context
The Fenwick Tree was proposed by Peter Fenwick in 1994 in a paper titled "A New Data Structure for Cumulative Frequency Tables". It was originally developed as a highly efficient mechanism for implementing arithmetic coding and data compression algorithms, where fast updates and prefix sum queries of dynamic frequency tables are crucial.
Real-world Applications
- Data Compression: Fundamental in maintaining cumulative frequency tables in adaptive arithmetic compression techniques.
- Inversion Counting: Used to efficiently count the number of inversions in an array, which is a measure of how far the array is from being sorted.
- Rank Queries: Helpful in scenarios where one needs to maintain a dynamic set of elements and efficiently query the rank of a given element or find the k-th smallest element.
Related Concepts
- Segment Tree — A more general and flexible tree structure that can handle a wider variety of range queries (like minimum/maximum) and range updates, though it consumes more memory.
- Prefix Sums — A simple static array approach that allows O(1) range sum queries but requires O(n) time for point updates.
Experience it interactively
Adjust parameters, observe in real time, and build deep intuition with Riano’s interactive Fenwick Tree (BIT) module.
Try Fenwick Tree (BIT) on Riano →