A Fenwick tree, also known as a Binary Indexed Tree (BIT), is a data structure that provides efficient methods for calculating prefix sums and performing point updates in an array. It was invented by Peter M. Fenwick in 1994 to improve the efficiency of arithmetic coding operations. The structure combines the benefits of both arrays and trees, offering logarithmic time complexity for both query and update operations.
Structure and Implementation
The Fenwick tree is implemented using a simple array where each element at index i stores the sum of a specific range of elements from the original array. The key insight is that any positive integer can be represented as a sum of distinct powers of two, and this binary representation determines which ranges each node in the tree covers.
For a Fenwick tree storing n elements, the tree array typically has size n+1 (with index 0 unused for simplicity). The parent-child relationships are determined using bitwise operations. Specifically, for any index i, its parent is i + (i & -i), where & is the bitwise AND operator and -i is the two's complement of i.
Each node at index i contains the sum of elements in the range [i - (i & -i) + 1, i]. For example, node 12 (binary 1100) stores the sum of 4 elements because 12 & -12 = 4, covering the range from index 9 to 12.
Operations
The two primary operations supported by Fenwick trees are prefix sum queries and point updates, both executable in O(log n) time.
Prefix Sum Query: To calculate the sum of elements from index 1 to index k, the algorithm starts at index k and moves toward index 1 by repeatedly subtracting the least significant bit. The sum accumulates values stored at each visited node. The operation i -= (i & -i) efficiently navigates to the next relevant node.
Point Update: To add a value delta to the element at index k, the algorithm starts at index k and propagates the change upward by moving to parent nodes using i += (i & -i) until exceeding the array bounds. Each visited node incorporates the delta into its stored sum.
Range Query: For sum queries between arbitrary indices l and r, the result equals prefix_sum(r) - prefix_sum(l-1).
Time and Space Complexity
Fenwick trees provide optimal logarithmic complexity for their primary operations. Both point updates and prefix sum queries require O(log n) time, where n is the number of elements. This efficiency stems from the binary representation properties that limit the number of nodes involved in any operation to at most the number of bits in the index.
The space complexity is O(n), requiring exactly one array element per original data element. This makes Fenwick trees more space-efficient than segment trees, which typically require 2n-1 nodes for n elements.
The initialization of a Fenwick tree from an array can be performed in O(n) time using a specialized algorithm, rather than the naive O(n log n) approach of performing n individual updates.
Applications
Fenwick trees find extensive use in computational problems requiring frequent prefix sum calculations and updates. Common applications include:
Inversion Counting: Efficiently counting the number of elements greater than a given value that appear before it in an array, useful in ranking and sorting problems.
Order Statistics: Maintaining dynamic frequency counts to quickly determine the k-th smallest element or rank of elements.
Algorithmic Competitions: Frequently appearing in programming contests due to their simplicity and efficiency for problems involving cumulative frequency tables.
Data Compression: Originally designed for arithmetic coding, where cumulative frequency counts are essential for encoding and decoding operations.
Computational Geometry: Supporting algorithms that require dynamic prefix sums over coordinate values.
Variations and Extensions
Several extensions enhance the basic Fenwick tree's capabilities. 2D Fenwick trees support efficient range queries and updates over rectangular regions in matrices, with O(log²n) complexity for operations.
Range Update, Point Query variants allow adding values to ranges of elements while querying individual positions, achieved through difference arrays.
Range Update, Range Query versions support both range updates and range queries, typically requiring two Fenwick trees or augmentation with additional data structures.
Sparse Fenwick trees optimize space usage when dealing with large indices but few actual elements, storing only non-zero nodes.
The structure can also be adapted for other associative operations beyond addition, such as multiplication or bitwise operations, provided the operation has an inverse or the problem structure allows.