Sign in to watch this lesson
Algorithms - Trees and Range Queries · 4:07
The Update-Query Trade-off
Prefix sums answer any range sum with one subtraction, but a single changed value forces the whole tail of the prefix array to be rewritten; a plain array is the mirror image. We place both on a plot of update cost against query cost, cut the array into blocks of about root n to bring the worse side down, and time all three on a Mac: each corner wins its own extreme, while the blocks win a realistic mix by more than ten times, setting up the logarithmic structures that come next.
You will learn
- Answer static range sums with a prefix array (P[r] - P[l] for [l, r)) and explain why it needs an operation with an inverse
- Explain why a point update costs O(n) with prefix sums and a range query costs O(n) with a plain array
- Implement square-root decomposition with block sums: O(1) point update, O(sqrt n) range query, and choose the block size
- Pick a structure from the workload's mix of updates and queries, and know that Fenwick and segment trees give O(log n) for both