Range minimums on an array that changes
A Fenwick tree keeps range sums fast while single values change, and it does so by writing each range sum as one prefix sum minus another. That works only for answers that can be subtracted. This lesson builds a segment tree, which answers questions such as the smallest value in a range in time and still lets us change any value in .
Take this array of eight values:
We want two operations on it. A range query asks for the minimum of a range of positions: the minimum of positions 0 to 3 is 2, and the minimum of positions 4 and 5 is 1. A point update sets one position to a new value: once position 1 is set to 3, the minimum of positions 0 to 3 is 3. The following problem asks for these two operations, with positions counted from 1.
You get an array of integers and queries of two kinds. 1 k u sets the value at position to . 2 a b asks for the smallest value among positions through . Positions count from 1.
Print the answer to every query of the second kind.
Constraints
Sample · Input
8 4 3 2 4 5 1 1 5 3 2 1 4 2 5 6 1 2 3 2 1 4
Output
2 1 3
The sample is our array. Its first query, 2 1 4, asks about the first four values, which are our positions 0 to 3, so the answer is 2. The update 1 2 3 sets the second value to 3, and the same query then answers 3.
The direct solution keeps the array as it is. An update writes one value, and a query scans its range. A range can hold all values, so on the largest input the queries cost up to
At about steps a second, roughly what C++ manages, that is 400 seconds, and the limit is one second. A loop written in Python is about ten times slower.
Prefix sums and Fenwick trees avoid the scan by subtracting: the sum of positions 6 and 7 is the sum of all eight values minus the sum of the first six. Minimums do not come apart like that. The minimum of all eight values is 1 and the minimum of the first six is also 1, and from those two numbers there is no way to work out the minimum of positions 6 and 7, which is 3. So in place of prefixes, a segment tree stores the minimums of ranges that can be put side by side to cover a query exactly.
Store the minimum of every half
A segment tree stores the minimum of the whole array, of its two halves, of the two halves of each half, and so on down to single positions. We name a range by a half-open pair [lo, hi): the positions from lo up to, but not including, hi. The whole array is [0, 8) and its halves are [0, 4) and [4, 8). Drawn with every range above its two halves, the stored minimums form a tree:
Each circle is a node. The node at the top, the root, covers the whole array. Each node in the bottom row is a leaf: it covers one position and holds that position's value. Every other node holds the smaller of the two values directly below it, the values of its two children. The root holds , and the node for [0, 4) holds .
The ranges follow one rule. A node that covers [lo, hi) and has more than one position splits at the midpoint mid, which is lo + hi halved and rounded down. Its left child covers [lo, mid) and its right child covers [mid, hi), so every position of a node belongs to exactly one of its children.
The rule does not need the length to be a power of two. Five values split into [0, 2) and [2, 5), and [2, 5) splits into [2, 3) and [3, 5). The halves are uneven and some leaves sit one row higher than others, but everything on this page works the same way on such a tree.
The tree is small. Every split turns one range into two, so reaching single positions from one range takes splits: an array of values has leaves and nodes above them, 15 nodes in all for our eight values.
The tree is also shallow. The root is at depth 0, its children are at depth 1, and so on, and the nodes at one depth form a level. Each level halves the ranges of the one above it, so eight values need 4 levels. An array of 200,000 values needs 19, because means 18 halvings below the root. Both operations do a small, fixed amount of work per level, which is where comes from.
Answer a query from a few whole nodes
Take the query for the minimum of positions 1 to 5, which is the range [1, 6):
Three nodes of the tree cover exactly these five positions without overlapping: [1, 2), [2, 4) and [4, 6).
Their stored minimums are 2, 4 and 1, so the answer is . The answer combines three stored numbers in place of five array values.
To find these nodes, we start at the root and compare each node's range with the query's range. There are three cases:
- The node is outside the query: the two ranges share no position. The node has nothing to contribute, and we go no further.
- The node is inside the query: every position of the node belongs to the query. We take its stored minimum and go no further, because that one number already accounts for everything below the node.
- The node is partly inside: some of its positions belong to the query and some do not. Its stored minimum might come from a position the query leaves out, so we cannot use it. We ask both children and take the smaller of their two answers.
For the range [1, 6), the walk visits these nodes in this order:
| Node | Case | What the walk does |
|---|---|---|
[0, 8) | partly inside | asks [0, 4) and [4, 8) |
[0, 4) | partly inside | asks [0, 2) and [2, 4) |
[0, 2) | partly inside | asks [0, 1) and [1, 2) |
[0, 1) | outside | nothing |
[1, 2) | inside | takes 2 |
[2, 4) | inside | takes 4 |
[4, 8) | partly inside | asks [4, 6) and [6, 8) |
[4, 6) | inside | takes 1 |
[6, 8) | outside | nothing |
The walk visits 9 of the 15 nodes and never looks below [2, 4) or [4, 6). On eight values that is more work than a scan, but the number of visits grows with the depth of the tree, not with the length of the range.
In general, a query visits at most four nodes on each level. On any one level, the nodes that overlap the query lie next to each other, and all of them are inside the query except possibly the first and the last, which can stick out past its two ends. At depth 2 in the table above, for example, the nodes that overlap [1, 6) are [0, 2), which is partly inside, and [2, 4) and [4, 6), which are inside.
So at most two nodes per level are partly inside, and only those send the walk on to the next level, to at most four children. For 200,000 values, where a scan could read all 200,000, a query visits at most
Try other ranges
Drag the two ends to change the query. Green nodes are inside the range and used whole, amber nodes are partly inside and split into their children, dashed nodes are outside, and faded nodes are never visited. The third preset is a range that visits as many nodes as any range can in this tree, and the last one is a tree over five values, with uneven halves.
Update one value and the nodes above it
Now set position 1 to 3, as the sample's update does. The leaf [1, 2) takes the new value. The only other nodes whose ranges contain position 1 are the ones on the way up from that leaf to the root, one on each level: [0, 2), [0, 4) and [0, 8). We recompute each of them from its two children, from the bottom up:
The root stays at 1, because its right child still holds a 1. Each node is recomputed from both of its children, not adjusted from its old value: the old minimum of [0, 2) was the very 2 that we replaced, so it says nothing about the new minimum, which has to be taken over both leaves again.
An update writes one node per level, so at most 19 nodes for 200,000 values.
Try other updates
Pick an index with the slider or by tapping a value in the bottom row. The highlighted nodes are the ones whose ranges contain it, and setting a new value recomputes them. The second preset is the update above. In the third, index 6 rises from 5 to 8 while its neighbour holds 3, so the minimum of the pair stays 3: every node above the leaf is recomputed and none of them changes. In the five-value tree, index 2 sits one level higher than index 4.
Store the tree in an array
The tree needs no node objects and no links between them. We lay its nodes out in an array in breadth-first order: level by level from the root down, and from left to right within a level. The root is stored at position 1, its left child at position 2, its right child at position 3, the left child of the left child at position 4, and so on. A node's position is its number , and tree[v] holds its value.
With this numbering, the children of node are nodes and , and its parent is halved and rounded down: node 3 has the children 6 and 7, and both have the parent 3. The reason is that the levels above depth hold nodes, so the first node at depth is number . If node is places after that first node, so that , the nodes before it on its level have children, which come first on the next level, so the left child of is number .
A heap stored in an array uses the same layout from position 0, where the children of node are and . Starting from 1 makes the formulas shorter.
tree underneath.With eight values the numbers run from 1 to 15 and none is skipped. When the length is not a power of two, some numbers go unused: the tree over five values uses nodes 1 to 7, 14 and 15. The numbers at depth run from to . The deepest depth is rounded up, which is below , so the largest number is below . We give the array entries and leave index 0 unused.
The three recursive functions
Each of the three functions below is recursive and takes a node number v together with that node's range [lo, hi), so a node never has to store its own range. Every call from outside starts at the root, as (1, 0, n).
INF = float("inf")
def build(v, lo, hi):
if hi - lo == 1:
tree[v] = nums[lo]
return
mid = (lo + hi) // 2
build(2 * v, lo, mid)
build(2 * v + 1, mid, hi)
tree[v] = min(tree[2 * v], tree[2 * v + 1])
def update(v, lo, hi, i, value): # nums[i] = value
if hi - lo == 1:
tree[v] = value
return
mid = (lo + hi) // 2
if i < mid:
update(2 * v, lo, mid, i, value)
else:
update(2 * v + 1, mid, hi, i, value)
tree[v] = min(tree[2 * v], tree[2 * v + 1])
def query(v, lo, hi, left, right): # min of nums[left:right]
if right <= lo or hi <= left:
return INF # outside
if left <= lo and hi <= right:
return tree[v] # inside
mid = (lo + hi) // 2
return min(query(2 * v, lo, mid, left, right),
query(2 * v + 1, mid, hi, left, right))
data = sys.stdin.read().split()
n, q = int(data[0]), int(data[1])
nums = [int(x) for x in data[2:2 + n]]
tree = [INF] * (4 * n)
build(1, 0, n)
out = []
pos = 2 + n
for _ in range(q):
kind, a, b = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])
pos += 3
if kind == 1:
update(1, 0, n, a - 1, b) # position a is index a - 1
else:
out.append(query(1, 0, n, a - 1, b))
print("\n".join(map(str, out)))On the sample input the program prints 2, 1 and 3.
build fills the leaves from nums and computes every other node after its two children, so it visits each node once. update follows the path to the leaf of index i, choosing a child by comparing i with mid, and recomputes each node on the way back up.
query is the three cases in order: outside, inside, partly inside. For a node outside the range it returns INF, infinity, which is larger than every value, so the min in the caller ignores it.
The problem counts positions from 1 and includes both ends of a range. Position is index , and positions through are the half-open range [a - 1, b).
This recursive form is the clearest one and the one the later pages extend, but Python pays for every function call. When a time limit is tight, use the loop version in the Deeper read below.
Worked example
Step through the sample
The trace builds the minimum tree for our array and then runs the sample's four operations. It shows one row per depth, each cell labelled with its node's range. Its queries are written with 0-based half-open ranges: [2, left, right] asks for the minimum of [left, right) and [1, i, value] sets index i, so the sample's 2 1 4 appears as [2, 0, 4].
The leaves hold the 8 values. Every other node covers [lo, hi) and splits at mid = (lo + hi) // 2.
Change the example input
Current result: [2,1,3]
Deeper read: the same tree without recursion
When point updates and range queries are the only operations, the tree can be written as two short loops. The leaves are stored at indices to of the array, so the leaf of index i is node i + n. Node still has the children and , and its parent is halved and rounded down. The array needs only entries.
INF = float("inf")
def update(i, value): # nums[i] = value
v = i + n # the leaf of index i
tree[v] = value
v //= 2
while v >= 1:
tree[v] = min(tree[2 * v], tree[2 * v + 1])
v //= 2
def query(left, right): # min of nums[left:right]
best = INF
lo, hi = left + n, right + n # leaves lo .. hi - 1
while lo < hi:
if lo % 2 == 1: # lo is a right child: use it alone
best = min(best, tree[lo])
lo += 1
if hi % 2 == 1: # hi - 1 is a left child: use it alone
hi -= 1
best = min(best, tree[hi])
lo //= 2
hi //= 2
return best
data = sys.stdin.read().split()
n, q = int(data[0]), int(data[1])
tree = [INF] * n + [int(x) for x in data[2:2 + n]] # leaves at n .. 2n - 1
for v in range(n - 1, 0, -1):
tree[v] = min(tree[2 * v], tree[2 * v + 1])
out = []
pos = 2 + n
for _ in range(q):
kind, a, b = int(data[pos]), int(data[pos + 1]), int(data[pos + 2])
pos += 3
if kind == 1:
update(a - 1, b) # position a is index a - 1
else:
out.append(query(a - 1, b))
print("\n".join(map(str, out)))On the sample input the program prints 2, 1 and 3.
update sets a leaf and walks up: it halves v until it has passed the root. query starts at the leaves of the two ends of the range and moves up one level per round. Between rounds, lo and hi mark the nodes not yet counted, lo included and hi not.
If lo is odd, it is a right child, and its parent would also cover the node to its left, which the range leaves out. So the query takes node lo by itself and steps past it. The right end is the mirror image: if hi is odd, node hi - 1 is a left child whose parent would also cover node hi, outside the range, so the query steps back and takes node hi - 1 by itself. Then both ends move up to their parents.
When is not a power of two, the nodes above the leaves no longer cover the halves drawn on this page, but the loops still return the right answers. They work for any and for any way of combining in which the order of the two sides does not matter, such as minimum, maximum and sum.
In Python the saving is worth having. On 200,000 values and 200,000 queries, the loop version took a little over half the time of the recursive program in our runs, and the USACO Guide reports that its recursive Python tree exceeds the one-second limit on CSES.
Store sums in the same tree
Nothing in the shape of the tree depends on the minimum. To answer range sums, every node stores the sum of its range. A leaf still holds its value, and two places in the code change together:
- Every
minbecomes a sum. Inbuildand inupdate, a node istree[2 * v] + tree[2 * v + 1], andqueryadds the answers of the two children. - A node outside the query returns 0, which leaves a sum unchanged the way infinity leaves a minimum unchanged.
The walk itself does not change. For the range [1, 6), the same three nodes are inside the query, they now hold 2, 9 and 2, and the answer is . Maximums work the same way with max and minus infinity. The Custom combine rules page says which answers a segment tree can store and which it cannot.
When to use a segment tree
Range sums with point updates are the problem the Fenwick tree already solves, and for that problem the Fenwick tree is the better tool: two short loops and an array of entries. The segment tree is for the questions a Fenwick tree cannot answer, such as minimums.
| Structure | Updates | Range questions | Cost |
|---|---|---|---|
| Prefix sums | none | sum, count, XOR | to build, then per question |
| Fenwick tree | one position at a time | sum, count, XOR | per operation |
| Segment tree | one position at a time | minimum, maximum, sum and anything else two halves can be combined into | per operation |
The segment tree can also be extended in ways the other two cannot. The later pages of this lesson give it nodes that store several values each, and updates that change a whole range in one operation.
Cost of the operations
- Build
- Each of the nodes is written once.
- Range query
- At most four nodes on each level: 76 for .
- Point update
- One node on each level: 19 for .
- Memory
- An array of entries for the recursive tree, or for the loop version.
At the problem's limits, 200,000 operations of at most 76 node visits each come to about steps, where scanning needed .
Common segment tree mistakes
Returning 0 for a node outside a minimum query.
- Where it breaks
- On our array, the minimum of
[0, 4)comes out as0: the node[4, 8)is outside the query and returns 0. The answer is2. - The fix
- Return a value that cannot change the result: infinity for a minimum, minus infinity for a maximum, 0 for a sum.
Using a node's stored value when the node is only partly inside the query.
- Where it breaks
- If the test for "inside" is replaced by "the ranges overlap", the minimum of
[2, 4)stops at the root and returns1, the minimum of the whole array. The answer is4. - The fix
- Use a node whole only when its entire range lies in the query, which is what the second test in
querychecks.
Giving the recursive tree an array of entries.
- Where it breaks
- With five values, the recursion uses nodes 14 and 15, past the end of a 10-entry array.
- The fix
- Allocate entries.
Setting the leaf and leaving the nodes above it alone.
- Where it breaks
- After position 1 is set to 3, the node
[0, 2)still holds 2, so the sample's last query prints2. The answer is3. - The fix
- After setting a leaf, recompute every node on the way back to the root.
Recall After position 1 is set to 3, which nodes does the minimum of `[1, 7)` use whole, and why is `[0, 2)` not one of them?
The values are now 3, 3, 4, 5, 1, 1, 5, 3. The query uses [1, 2) with 3, [2, 4) with 4, [4, 6) with 1 and [6, 7) with 5, so the answer is . The node [0, 2) is only partly inside: its stored minimum could come from position 0, which the query leaves out, so the walk asks its two children and uses only [1, 2).