Range queries

A dashboard where the past keeps changing

A merchant dashboard gets a new box that shows sales between any two times today, to the second. A day has 86,400 seconds, so the code keeps one total per second and a prefix sum over them. Any range is then one subtraction, and the demo works well.

Then the evening rush starts. Refunds and failed settlements arrive late, and each one corrects the total for a second that has already passed. In the busiest hour there are about 50,000 corrections and 50,000 range queries, mixed together.

A correction to an early second changes every prefix after it, which can mean up to 86,400 rewrites. Do the sum: 50,000 corrections like that are about 4.3 billion writes in an hour. If you drop the prefix sums and add up each range from scratch instead, a correction becomes one write, but a query becomes up to 86,400 additions: the same 4.3 billion, moved to the queries. One version stores nothing beyond the raw seconds; the other stores every prefix. The question is what to store in between.

Pause and predict What could you store so that a correction and a query are both cheap?

Store sums of blocks, sized by the lowest bit

Prefix sums, from Unit 4, answer any range sum in O(1), but they assume the array never changes. If one value changes, every prefix after it is wrong, so an update costs O(n).

Pause and predict 10⁵ updates and 10⁵ range sums, interleaved, over 10⁵ values, using prefix sums. Roughly how many steps?

The way out is to store something in between: sums of ranges, chosen so that each position lies inside only about log n of them, and each prefix can be split into only about log n of them. An update fixes the few ranges that contain the position, and a query adds up the few that together cover the prefix. Metrics systems store sums over blocks of time for the same reason: rollups in a metrics store.

The Fenwick tree

Number the positions from 1. Let lowbit(i) be the value of the lowest set bit of i, computed as i & -i. For example, lowbit(6) = 2, lowbit(8) = 8 and lowbit(7) = 1. A Fenwick tree keeps one array, tree, where tree[i] holds the sum of the lowbit(i) values that end at position i. For n = 8, written t1 to t8: t1 holds position 1, t2 holds positions 1 and 2, t3 holds 3, t4 holds 1 to 4, t5 holds 5, t6 holds 5 and 6, t7 holds 7, and t8 holds all eight.

Pause and predict With n = 8, which stored sums add up to positions 1 to 7?

The numbering is where mistakes happen. lowbit(0) = 0, so a walk that reaches 0 never moves again, and an update that starts at position 0 loops forever. That is why the tree is numbered from 1. LeetCode's index k is stored at k + 1, and in the query walk, reaching i = 0 means there is nothing left to add.

The segment tree

Pause and predict Range maximum with updates. Can a Fenwick tree answer max(l..r) as prefix(r + 1) and prefix(l) combined?

Each node covers a range [l, r] and stores the combined value for that range. A leaf covers one element. An inner node splits its range at mid = (l + r) / 2, and its value combines its two children's values: their sum, or their max. The tree is about log n levels deep.

A query visits nodes starting from the root. A node whose range is entirely outside the query range is skipped. A node entirely inside it is used whole, without visiting its children. A node partly inside is split, and both children are visited. At most two nodes per level are used whole, so a query costs O(log n). An update changes one leaf and recomputes the nodes above it, which also costs O(log n).

How to recognise it

The first question to ask is whether the array changes between queries. If it does not, prefix sums are enough and you need nothing from this unit. If it does, ask what the query combines, because that decides which tree to use.

Pause and predict An array changes, and the queries ask for the maximum of a range. Which tool?

Problems that only look like it

• Range sums on an array that never changes. Use prefix sums: each query is O(1), and there is little to get wrong.
• The maximum of every window as it slides along. The windows only ever move to the right, so a monotonic deque finds every maximum in O(n). That is in the stack unit, and needs no tree.
• The k largest values, or the median of a stream. The question is about the whole set, not a range of positions, so use heaps.
• Many additions to ranges, read only once at the end. Use a difference array, from prefix sums.

Where it bites

Pause and predict An update sets position 4 from 7 to 10. What do you add along the climb?

• Numbering the Fenwick tree from 0. lowbit(0) is 0, so the walk never moves. Store index k at k + 1.
• Writing i < n in the update walk. Then tree[n], which covers the most positions, is never updated.
• Computing prefix(r) instead of prefix(r + 1). The range then leaves out its right end.
• Adding the new value instead of the difference when an update sets a value. The old value stays in every block.
• Using a Fenwick tree for a range max or min. A max cannot be undone by subtracting, so use a segment tree.
• Giving a segment tree an array of 2n slots. The recursive layout, with children 2i and 2i + 1, needs up to 4n slots when n is not a power of two.