Segment tree

A segment tree answers queries about a range of an array, such as "what is the smallest element between positions $l$ and $r$?", while elements of the array change: both a query and an update take O(\log n) time. For sums only, a Fenwick tree is shorter; for an array that never changes, a sparse table answers the minimum in $O(1)$.

Take the array 6, 3, 8, 5, 9, 4, 7, 2 at positions 1 to 8. The minimum of positions 2 to 6 is 3. Now an update sets position 2 to 10, and the same query has a new answer, 4.

Scanning the range takes $O(n)$ per query (time complexity), and running minima can't be subtracted the way prefix sums can.

How it works

A segment tree is a binary tree: its top node is the root, each node has two children below it, and the nodes at the bottom are leaves.

Each node covers a range of positions. The root covers the whole array, 1..8, and holds its minimum. Each node splits its range into two halves, left half first, and has a child for each: the halves of 1..8 are 1..4 and 5..8. A node that covers one position is a leaf and holds that element. Every other node holds the smaller of its two children's values.

Fig. 1. Each box holds the minimum of the positions under it. The bottom row is the array.

8 elements give 15 nodes on 4 levels. In general there are 2n - 1 nodes and about \log_2 n + 1 levels.

To find the minimum of positions 2 to 6, start at the root and ask each node how its range meets 2..6. There are three cases:

• Outside: the node covers no position from 2..6. It adds nothing.

• Inside: the node's range lies within 2..6. It gives its stored value at once, without looking further down.

• Split: the node's range is partly inside. It passes the query to both children and takes the smaller of their answers.

For 2..6 the query uses the inside nodes 2..2, 3..4 and 5..6 and answers min(3, 5, 4) = 3 (Fig. 2).

Fig. 2. The blue nodes lie side by side over exactly positions 2 to 6.

The query is fast because few nodes are split. A split node covers position 2 or position 6, the ends of the range, but not the whole range between them. The nodes on one level don't overlap, so at most 2 of them cover an end, and at most 2 per level are split. Their children are at most 4 nodes on the next level, so a query visits at most 4 nodes per level: about 4 \log_2 n in total, under 70 for 10^5 elements.

The nodes that cover one position form a path from its leaf up to the root, one node per level (Fig. 3). An update goes down to the leaf and sets it. Then, on the way back up, it recomputes each node on the path from its two children.

Fig. 3. Position 7 and its path to the root.

To build the tree, a leaf takes its element, and any other node first builds its two children and then takes the smaller of their values. Each of the 2n - 1 nodes costs one comparison, so the build takes $O(n)$.

Here is the update that sets position 2 to 10, followed by two queries.

Set position 2 to 10. The update starts at the root 1..8; the blue ring marks the nodes it goes down through.

Position 2 lies in 1..4, so the update goes down to 1..4.

Position 2 lies in 1..2, so the update goes down to 1..2.

The leaf 2..2 is set from 3 to 10.

On the way up, 1..2 is recomputed: min(6, 10) = 6, no longer 3.

On the way up, 1..4 is recomputed: min(6, 5) = 5, no longer 3.

The root 1..8 is recomputed too: min(5, 2) = 2, so it stays 2.

The update is done: nodes 1..2 and 1..4 now hold 6 and 5.

Minimum of positions 2 to 6. The root 1..8 is split: the blue ring marks split nodes, blue nodes are inside, grey ones outside.

1..4 is split: the query goes to both of its halves.

1..2 is split: the query goes to both of its halves.

1..1 is outside 2..6 and adds nothing.

2..2 is inside 2..6 and gives its value 10.

3..4 is inside 2..6 and gives its value 5.

5..8 is split: the query goes to both of its halves.

5..6 is inside 2..6 and gives its value 4.

7..8 is outside 2..6 and adds nothing.

The answer is min(10, 5, 4) = 4.

Minimum of positions 1 to 4. The root 1..8 is split.

1..4 is inside 1..4 and gives its value 5.

5..8 is outside 1..4 and adds nothing.

The answer is 5, from the single inside node 1..4.

1/22

Fig. 4. Step through the update and the queries with the buttons or the arrow keys. The last query uses a single inside node.

In C++

The standard library has no segment tree. The root is node 1, and the children of node v are 2 * v and 2 * v + 1. In Fig. 1, node 1..8 is 1, 1..4 and 5..8 are 2 and 3, and the leaves are 8 to 15. The values are kept in a vector t, with t[v] the value of node v.

The three functions are recursive. Each gets a node as (v, tl, tr): its number and the range tl..tr it covers. The middle tm = (tl + tr) / 2 splits a node into tl..tm and tm + 1..tr. build fills the tree, query returns the minimum of positions l to r, and update sets position p to x. A node outside the range returns INF, a number larger than any element, so it never changes a minimum. This is the neutral value of min.

The input is n and q, then n numbers, then q lines, each Q l r (print the minimum of positions l to r) or A p x (set position p to x). The example above is this input:

8 4
6 3 8 5 9 4 7 2
Q 2 6
A 2 10
Q 2 6
Q 1 4

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 2000000000;   // larger than any element: the neutral value for min
int n;
vector<int> a, t;

// build from the children: fill node v, which covers tl to tr
void build(int v, int tl, int tr) {
    if (tl == tr) { t[v] = a[tl]; return; }
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    t[v] = min(t[2 * v], t[2 * v + 1]);
}

// the minimum of positions l to r inside node v, which covers tl to tr
int query(int v, int tl, int tr, int l, int r) {
    if (r < tl || tr < l) return INF;           // outside: contributes nothing
    if (l <= tl && tr <= r) return t[v];        // inside: take the stored value
    int tm = (tl + tr) / 2;                     // split: ask both halves
    return min(query(2 * v, tl, tm, l, r), query(2 * v + 1, tm + 1, tr, l, r));
}

// set position p to x
void update(int v, int tl, int tr, int p, int x) {
    if (tl == tr) { t[v] = x; return; }         // go down to the leaf
    int tm = (tl + tr) / 2;
    if (p <= tm) update(2 * v, tl, tm, p, x);
    else update(2 * v + 1, tm + 1, tr, p, x);
    t[v] = min(t[2 * v], t[2 * v + 1]);         // recompute on the way up
}

int main() {
    int q;
    cin >> n >> q;
    a.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) cin >> a[i];
    t.assign(4 * n, 0);
    build(1, 1, n);
    while (q--) {
        char c;
        int x, y;
        cin >> c >> x >> y;
        if (c == 'Q') cout << query(1, 1, n, x, y) << '\n';
        else update(1, 1, n, x, y);
    }
}

The program reads positions from 1 and calls the functions with (1, 1, n). For positions from 0, call them with (1, 0, n - 1).

Fig. 5. Node numbers for 6 elements.

Sum, maximum and other operations

To keep another operation, change the two min calls to its combine and INF to its neutral value:

The combine must give the same result whichever way the halves are grouped: min(min(6, 3), 8) = min(6, min(3, 8)) = 3. The average doesn't. Averaging 6 and 3 gives 4.5, and then with 8 gives 6.25, while 6 averaged with the average of 3 and 8 gives 5.75. Store the sum and the count instead, and divide at the end. For some operations the order of the halves matters too (problem 5662 multiplies matrices), so always put the left child first.

Examples of use

A node can store several numbers, as long as the numbers of two children give the numbers of their parent.

Two numbers in a node

Problem 4483 asks whether two elements of l..r sum to at most k, while elements change. The best pair is the two smallest elements, so each node keeps two numbers: the smallest and the second smallest of its range. The combine takes the two smallest of the four numbers of its children, and an outside node returns two INFs.

Four numbers in a node

For the largest sum of consecutive elements inside l..r (problem 2907), one number per node is not enough: the best part of a range can cross the middle. Each node keeps its sum, its best prefix sum, its best suffix sum and its best sum anywhere inside. A parent's best prefix is the larger of the left best prefix and the left sum plus the right best prefix; the best suffix is the mirror image. Its best inside is the largest of the children's best ones and the left best suffix plus the right best prefix.

The first element at least x

In problem 2832, each order is poured from the first barrel that holds at least x liters. Keep a tree of maxima. The maximum of positions 1 to r only grows with r, so a binary search on r with query finds the first barrel in O(\log^2 n). Going down from the root, into the left child whenever its maximum is at least x, finds it in O(\log n).

Common mistakes

• Returning 0 for a node outside the range when the tree keeps minima. On the example, the query for 2..6 visits the outside nodes 1..1 and 7..8 and prints 0 instead of 3. Return the neutral value of the operation from the table above.

• Updating only the leaf, or updating each node on the path with min(t[v], x). After position 2 is set from 3 to 10, node 1..4 keeps 3, and the query for 1..4 prints 3 instead of 5. Recompute each node on the path from its two children.

• Leaving out the "inside" case, so every query goes down to the leaves. The answers stay right, but the query for 1..8 visits all 15 nodes instead of 1. Return t[v] as soon as the node is inside the range.

Similar structures

A Fenwick tree also updates one element and answers a range query in O(\log n), with shorter code and $n$ cells of memory. It gets a range as one prefix minus another, so it works only for operations that can be undone, such as the sum and XOR. Problem 695 needs the minimum and the maximum of a changing array, so it needs a segment tree.

A sparse table answers the minimum, the maximum or the gcd of an array that never changes in $O(1)$, but an update can rewrite about $n$ of its cells.

Lazy propagation extends the segment tree to updates of a whole range, such as adding x to every element from l to r, still in O(\log n).

Practice