Course contentsShow
← Computer Science
Lesson 653 of 2,87215. Tries and Specialized TreesFree lesson

Prefix Sum Query Operation

Computing prefix sums in O(log n) time by traversing and accumulating values from ancestor nodes in the Fenwick tree.

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:

  1. Start with sum = 0 and your target index i
  2. Add the value at tree[i] to your sum
  3. Remove the rightmost set bit from i (using i -= (i & -i))
  4. Repeat steps 2-3 until i becomes 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.