Fenwick Tree
A Fenwick tree, also called a Binary Indexed Tree (BIT), is a data structure that supports prefix sum queries and point updates in O(log N) time with O(N) ...
Binary Indexed Tree Concept
A Fenwick tree, also called a Binary Indexed Tree (BIT), is a data structure that supports prefix sum queries and point updates in O(log N) time with O(N) space. It was introduced by Peter Fenwick in 1994 as a simpler alternative to segment trees for the specific case of cumulative frequency tables and prefix sums. While less general than a segment tree, a Fenwick tree is remarkably compact in both code and memory, making it a favorite in competitive programming.
The Fenwick tree stores values in an array indexed from one (not zero). The key insight is that each position i in the Fenwick array stores the sum of a specific range of original array elements. The length of this range is determined by the lowest set bit of i in binary. For example, index 6 in binary is 110, with lowest set bit being 2, so it stores the sum of two elements: original[5] and original[6].
This range decomposition based on lowest set bits allows prefix sums to be computed by traversing parent-child relationships using bitwise operations. The update and query operations each touch at most O(log N) nodes.
Update and Query Using Bit Tricks
The two fundamental operations are update and prefix query. To update index i by adding delta: set tree[i] plus equals delta, then move to the next responsible index by adding the lowest set bit of i (computed as i plus (i AND minus-i)) and repeat until i exceeds N. To query the prefix sum from index 1 to i: accumulate tree[i] into the result, then move to the previous responsible index by subtracting the lowest set bit (i minus (i AND minus-i)) and repeat until i reaches zero.
The expression i AND (negative i) isolates the lowest set bit in two's complement arithmetic. This is a constant-time bitwise operation, making each step of update and query O(1). Since the number of set bits in any integer up to N is at most log base 2 of N, both operations run in O(log N).
Range sum queries between L and R are answered as prefix(R) minus prefix(L minus one). Point queries on the original array require storing a separate array of original values or computing the point value as prefix(i) minus prefix(i minus one).
Worked Example and Comparison with Segment Tree
Worked example: given array [2, 1, 1, 3, 2, 3, 4, 5], build a Fenwick tree. Index 1 stores 2, index 2 stores 3 (sum of indices 1-2), index 3 stores 1, index 4 stores 7 (sum of indices 1-4), index 5 stores 2, index 6 stores 5 (sum of indices 5-6), index 7 stores 4, index 8 stores 21 (sum of all). To query prefix sum from 1 to 6: tree[6] plus tree[4] equals 5 plus 7 equals 12. Verify: 2 plus 1 plus 1 plus 3 plus 2 plus 3 equals 12. Correct.
Updating index 3 (add 4): tree[3] plus equals 4, tree[4] plus equals 4, tree[8] plus equals 4. Three operations in O(log 8) equals 3 steps.
Interview tip: choose a Fenwick tree over a segment tree when the operation is a prefix sum or another invertible aggregate (subtraction must reverse the combination). Fenwick trees require roughly three to five lines of code per operation versus fifteen to thirty for a segment tree. When the problem involves non-invertible queries like range minimum, you must use a segment tree. Demonstrating awareness of this tradeoff shows mature algorithmic judgment.