Arrays and searching 0/121

Segment trees for range queries and updates · 1 of 3 Advanced

Point updates and range queries

Answer range minimums and sums while single values change, with a tree whose every node stores the answer for its own range.

3,463 words · 16 min read

Part 1 of 9 Range minimums with updates

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 O(log⁡n)O(\log n) time and still lets us change any value in O(log⁡n)O(\log n).

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 nn integers and qq queries of two kinds. 1 k u sets the value at position kk to uu. 2 a b asks for the smallest value among positions aa through bb. Positions count from 1.

Print the answer to every query of the second kind.

Constraints

  • 1≤n,q≤2⋅1051 \le n, q \le 2 \cdot 10^5
  • 1≤xi,u≤1091 \le x_i, u \le 10^9
  • 1≤k≤n1 \le k \le n
  • 1≤a≤b≤n1 \le a \le b \le n

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 nn values, so on the largest input the queries cost up to

2×105×2×105=4×1010 steps2 \times 10^5 \times 2 \times 10^5 = 4 \times 10^{10} \text{ steps}

At about 10810^8 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.