What is a Fenwick Tree (Binary Indexed Tree)?
A **Fenwick Tree** (also known as a **Binary Indexed Tree** or **BIT**) is a highly efficient tree-like data structure represented implicitly inside a flat 1D array. It is primarily used to perform dynamic prefix sum queries and point updates in logarithmic time.
Compared to a Segment Tree, a Fenwick Tree requires far less memory space ($N$ elements instead of $4N$) and is significantly easier to implement using smart bitwise arithmetic.
Bit Manipulation & The LSB
The core mechanism of a Fenwick Tree revolves around index manipulation using the **Least Significant Bit (LSB)** of index binary representations:
LSB(i) = i & (-i)
- Update key step: To propagate a point update at index i, we repeatedly add its LSB (i ← i + LSB(i)) to correct dependent node values up the array bounds.
- Query prefix sum step: To query the sum from index 1 to i, we repeatedly subtract its LSB (i ← i - LSB(i)) to merge segment ranges backwards.
Performance and Space
- Prefix Sum Query Time: O(log N)
- Point Update Time: O(log N)
- Space Complexity: O(N) - exact space match!