Prefix Sum Query Operation
What you'll learn: How to efficiently compute the sum of elements from index 0 to any index i in O(log n) time using a Fenwick tree.
The Core Idea
After building your Fenwick tree with point updates, you need a way to query prefix sums quickly. The Fenwick tree's structure lets you compute the sum of elements from the start up to any index by traversing upward through the tree, accumulating values from specific ancestor nodes.
The key insight: instead of summing all elements one-by-one (which would be O(n)), you exploit the binary representation of indices. Each position in the Fenwick tree stores a partial sum covering a range determined by the rightmost set bit in its index.
How It Works
To find the prefix sum up to index i:
- Start with
sum = 0and your target indexi - Add the value at
tree[i]to your sum - Remove the rightmost set bit from
i(usingi -= (i & -i)) - Repeat steps 2-3 until
ibecomes 0
This path follows the "parent chain" in the Fenwick tree's implicit structure, collecting exactly the ranges needed to cover [0...i].
Example Walkthrough
To query prefix sum up to index 6:
- Add
tree[6](covers range based on binary 110) - Remove rightmost bit: 6 → 4
- Add
tree[4](covers another range) - Remove rightmost bit: 4 → 0
- Done! Sum computed in 2 steps instead of 6
The number of steps equals the number of set bits in the binary representation, which is at most log n.
Key Takeaway: Prefix sum queries in a Fenwick tree take O(log n) time by strategically accumulating values along an ancestor path determined by flipping rightmost set bits in the index.