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

Range Query and Range Update

Performing range sum queries using prefix sums and implementing range updates using difference arrays with Fenwick trees.

Range Query and Range Update

You'll learn: How to efficiently perform range queries and updates using Fenwick Trees by leveraging prefix sums and difference arrays.

The Core Challenge

You've already seen how to handle point updates and prefix sum queries with Fenwick Trees. But what if you need to answer queries like "sum from index L to R" or make updates like "add X to all elements from L to R"? Doing these naively would be inefficient.

Range Queries with Prefix Sums

A range sum query asks for the sum of elements from index L to R. The key insight: this equals prefixSum(R) - prefixSum(L-1).

Think of it like measuring a rope segment. If you know the length from the start to point R and the length from the start to point L-1, the difference gives you the segment length between them.

With your Fenwick Tree's prefix sum operation, you simply query twice and subtract—still O(log n) time!

Range Updates with Difference Arrays

Range updates (e.g., "add 5 to all elements from index 3 to 7") seem expensive—updating each element individually takes O(n) time.

The clever trick: maintain a difference array where diff[i] represents the change at position i. To add X to range [L, R]:

  • Add X at position L (start of change)
  • Subtract X at position R+1 (end of change)

When you compute prefix sums of this difference array, the changes automatically propagate across the range! Your Fenwick Tree can store this difference array, making range updates O(log n) using two point updates.

To get the actual value at any position, query the prefix sum of the difference array.

Key Takeaway: Range queries reduce to two prefix sum queries via subtraction, while range updates become efficient using a difference array stored in a Fenwick Tree—both operating in O(log n) time.