Fenwick Tree Intro
A Fenwick Tree (Binary Indexed Tree) is a data structure that efficiently supports two operations on an array: point updates and prefix sum queries, both in O(log n) time. It is simpler and uses less memory than a segment tree for these specific operations.
Named after its inventor Peter Fenwick, it is widely used in competitive programming for range queries with point updates.
Key concept: each index i stores the sum of a range of elements determined by the least significant bit (LSB) of i. The LSB can be obtained as `i & -i`.
For an array of size n, we allocate a BIT array of size n+1 (1-indexed).
Basic operations:
- update(idx, delta) – add delta to the element at idx and propagate to all BIT nodes that cover idx.
- query(idx) – return prefix sum from 1 to idx by summing BIT nodes while decreasing idx by its LSB.
Two Minute Drill
- Fenwick Tree supports point update and prefix sum in O(log n).
- Uses less memory than segment tree (size n+1).
- Based on binary representation and LSB.
- 1-indexed internally; index 0 is dummy.
Need more clarification?
Drop us an email at career@quipoinfotech.com