The Segment Tree

Lesson 11 of 11 · Data structures

A segment tree divides an array into intervals (segments) and remembers a result for each of them – the sum, the minimum, the maximum or the GCD. A query for any interval and an update of one element take O(log n).

Before you start: prerequisites – The Fenwick tree, Introduction to recursion.
How to learn: type in and run every example, and solve the tasks at the end on your own first; open the hint and the solution only after that. All programs are in C++.

The idea

The root of the tree corresponds to the whole array [0, n−1]. Every node that covers [l, r] has two children: [l, m] and [m+1, r], where m = (l+r)/2. The leaves are single elements. In every node we keep the result for its interval – for the minimum: t[node] = min(t[left], t[right]).

We keep the nodes in an array as in a heap: the root is 1, the children of the node v are 2v and 2v+1. An array of length 4n is always enough.

  • A query [ql, qr]: if the node's interval is completely inside the query – return the node's value; if it is completely outside – return the neutral value (for the minimum: infinity); otherwise ask both children.
  • An update of position i: go down to the leaf, change it, and on the way back recompute all the ancestors.

Code: the minimum on an interval with updates

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

int n;
vector<int> a, t;

void build(int v, int l, int r) {
    if (l == r) { t[v] = a[l]; return; }
    int m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    t[v] = min(t[2 * v], t[2 * v + 1]);
}

int query(int v, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return INT_MAX;          // completely outside the query
    if (ql <= l && r <= qr) return t[v];           // completely inside the query
    int m = (l + r) / 2;
    return min(query(2 * v, l, m, ql, qr), query(2 * v + 1, m + 1, r, ql, qr));
}

void update(int v, int l, int r, int i, int x) {
    if (l == r) { t[v] = x; return; }
    int m = (l + r) / 2;
    if (i <= m) update(2 * v, l, m, i, x);
    else update(2 * v + 1, m + 1, r, i, x);
    t[v] = min(t[2 * v], t[2 * v + 1]);           // recompute the parent
}

int main() {
    int q;
    cin >> n >> q;
    a.resize(n);
    t.assign(4 * n, 0);
    for (int &x : a) cin >> x;
    build(1, 0, n - 1);
    while (q--) {
        int type, x, y;
        cin >> type >> x >> y;
        if (type == 1) update(1, 0, n - 1, x - 1, y);              // a[x] = y
        else cout << query(1, 0, n - 1, x - 1, y - 1) << "\n";     // min a[x..y]
    }
    return 0;
}

The input and output use positions from 1, and the tree works with positions from 0 – that is why there is x - 1.

Other operations and lazy propagation

For the sum write + instead of min and return 0 for an interval outside the query; for the maximum max and INT_MIN; for the GCD gcd and 0. When an update does not change one element but a whole interval (e.g. "add 5 to positions 3–10"), lazy propagation is used: the update is written into the node and pushed down to the children only when they are needed. More details: CP-Algorithms – Segment Tree.

Practice tasks

Every task has an example, a hint and a solution. The solutions have been checked on the examples from the text.

TASK 01Difficulty: medium

The sum on an interval

Change the segment tree so that it answers the query "the sum on the interval [l, r]" and supports the update "a[i] = v". The input format is the same as in the example from the lesson.

Example

Input

5 4
1 2 3 4 5
2 1 5
1 3 10
2 2 4
2 3 3

Output

15
16
10
TASK 02Difficulty: medium

The tallest building in a part of the street

There are n buildings of given heights in a street. Queries: B i h – building i is built up by h metres; M l r – what is the greatest height of a building from the l-th to the r-th?

Example

Input

5 4
10 30 20 40 15
M 1 3
B 3 15
M 1 3
M 4 5

Output

30
35
40
Common mistakes and tips
  • Let the array for the tree have 4n elements.
  • The neutral value must match the operation: 0 for the sum, infinity for the minimum, minus infinity for the maximum.
  • After an update you must recompute the parents on the way to the root.
  • If there are only sum queries without updates, prefix sums are enough; if there are updates and only sums – a Fenwick tree is shorter.

Check your knowledge

Open the quiz

Mini quiz: the segment tree

1. What are the children of node 5 in the array representation of the tree?




2. For the minimum, what does a query return for a node whose interval is completely outside the query?




3. What is the complexity of a query on an interval?