Segment trees

A segment tree is a data structure that allows efficient range query processing and updates on arrays.

In this section, array positions and query ranges are assumed to be 1-indexed unless said otherwise.

When we later implement the segment tree in C++, the original array a will be stored as a normal 0-indexed C++ array, while positions in queries and updates will remain 1-indexed.

What Is a Segment Tree

It is a binary tree where each node represents the answer to a query on a segment (subarray) of the original array. The tree is built using the following rules:

  • Leaf nodes represent a segment of length \(1\).
  • Each internal node represents a combination (sum, min, max, etc.) of its two children.

Let’s say that we have the following array [2, 4, 6, 8]. A sum segment tree built on this array looks as follows:

graph TD
    A["20 (1-4)"]
    B["6 (1-2)"]
    C["14 (3-4)"]
    D["2 (1-1)"]
    E["4 (2-2)"]
    F["6 (3-3)"]
    G["8 (4-4)"]

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

Note that the leaf nodes represent only one element, while every other node merges its children by taking the sum of their values.

Node Count and Padding

Let N be the number of leaf nodes in a segment tree after padding, and let n be the length of the original array.

Node Count

  • In a complete segment tree, the number of nodes at each level forms the sequence [1, 2, 4, …], i.e., powers of two.
  • Each power of two is equal to the sum of all previous powers of two plus 1.
  • Therefore, if the tree has N leaf nodes, the total number of nodes is 2N - 1.

Later, when storing the tree in an array, we will usually allocate 2N positions because index 0 is left unused. The actual tree nodes occupy indices 1 through 2N - 1.

Padding

  • If the original array has n elements and n is not a power of two, we pad the array with additional elements so that the number of leaf nodes N becomes the next power of two. The padding values must be chosen so that they do not affect the values of the other nodes.
  • In the worst case, we need to add fewer than n elements, because the next power of two is strictly less than 2n. Therefore, at most n - 1 padding elements are needed.

Example

If we change the previous example to [2, 4, 6], we need to add an element to make the length a power of two without affecting the other values. In this case, the best value to add is 0, since it does not change the sums of other nodes. The resulting segment tree will look like the following:

graph TD
    A["12 (1-4)"]
    B["6 (1-2)"]
    C["6 (3-4)"]
    D["2 (1-1)"]
    E["4 (2-2)"]
    F["6 (3-3)"]
    G["0 (4-4) padded"]

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

Representation

We will represent our segment tree as an array, giving an index to each node. The previous segment tree will be given indices as follows:

graph TD
    A["1: sum = 12 (1-4)"]
    B["2: sum = 6 (1-2)"]
    C["3: sum = 6 (3-4)"]
    D["4: sum = 2 (1-1)"]
    E["5: sum = 4 (2-2)"]
    F["6: sum = 6 (3-3)"]
    G["7: sum = 0 (4-4) padded"]

    A --> B
    A --> C
    B --> D
    B --> E
    C --> F
    C --> G

Each node i has children at positions 2 * i and 2 * i + 1, and its parent is at position i / 2.

In this example, the number of leaf nodes N is 4, which is also the index of the first leaf node. Therefore, a leaf node at segment-tree position i corresponds to the 1-indexed position i - N + 1 in the original array.

Equivalently, original-array position j corresponds to segment-tree position:

j + N - 1

For example, original-array position 1 is stored at seg[N].

Querying

Let’s define a function query(id, l, r, ql, qr) that returns the answer to a query from ql to qr, where:

  • id is the index of the current node.
  • l is the beginning of the interval covered by the current node.
  • r is the end of the interval covered by the current node.
  • ql is the beginning of the query range.
  • qr is the end of the query range.

All of l, r, ql, and qr are 1-indexed positions.

The function works as follows:

  1. If [ql, qr] and [l, r] are completely disjoint, discard the current node, as it does not contribute to the query.

  2. If [ql, qr] completely covers [l, r], return the value stored at the current node.

  3. Otherwise, split the range at the midpoint m = (l + r) / 2 and recurse on the children:

    • query(2 * id, l, m, ql, qr)
    • query(2 * id + 1, m + 1, r, ql, qr)

    Then merge the results from both children to obtain the answer for the current node.

To solve a query [ql, qr], call query(1, 1, N, ql, qr).

The time complexity of this algorithm is \(O(\log n)\).

Point Update

Some problems will ask us to update the value at 1-indexed position j to value v.

The leaf corresponding to position j is stored at:

j + N - 1

Therefore, we update the leaf node at position j + N - 1 and recompute the values of all its ancestors.

The number of ancestors is equal to the height of the tree, which is \(\log_2 N\). Since N is at most the next power of two after n, the complexity of a point update is \(O(\log n)\).

Implementation

When building a segment tree, we have two things: the original C++ array a, which is 0-indexed, and its size n.

The segment tree itself will be stored using 1-indexed node indices:

  • seg[1] is the root.
  • The children of seg[i] are seg[2 * i] and seg[2 * i + 1].
  • seg[0] is unused.

Positions used by queries and updates are also 1-indexed. Therefore:

  • array position j corresponds to a[j - 1];
  • array position j corresponds to segment-tree leaf seg[j + N - 1].

Tree Size

First, we need to compute the number of leaves N, which is the first power of two that is at least n. We find it by starting at 1 and doubling until it is big enough:

int N = 1;
while (N < n) {
    N *= 2;
}

For example, if n is 5 the loop gives N = 8, and if n is already a power of two the loop stops immediately and leaves N equal to n.

We need 2*N array positions. Since N is computed at runtime here, we can use a vector:

vector<int> seg(2 * N);

Although the tree contains only 2N - 1 nodes, position 0 is unused, so indices 1 through 2N - 1 must be available.

Building The Tree

We’ll write the code to build a sum segment tree.

Leaves Construction

To build the tree, we first need to put the leaves’ values.

The original C++ array a is 0-indexed, so a[i] represents the conceptual 1-indexed position i + 1. That position is stored at segment-tree index N + i.

for (int i = 0; i < n; i++) {
    seg[i + N] = a[i];
}

Then we pad new elements to complete the leaves.

for (int i = n + N; i < 2*N; i++) {
    seg[i] = 0;  // padded value depends on the segment tree
}

Internal Nodes Construction

To build the internal nodes, we’ll loop over them in reverse order and merge their children.

for (int i = N - 1; i > 0; i--) {
    seg[i] = seg[i * 2] + seg[i * 2 + 1];  // merging children's values
}

Queries

The query positions ql and qr, as well as the node intervals l and r, are all 1-indexed.

int query(int id, int l, int r, int ql, int qr) {
    // check if disjoint
    if (ql > r || l > qr) {
        return 0;
    }
    // check if [ql, qr] fully covers [l, r]
    if (ql <= l && r <= qr) {
        return seg[id];
    }
    // recurse and merge
    int m = (l + r) / 2;
    return query(id * 2, l, m, ql, qr) + query(id * 2 + 1, m + 1, r, ql, qr);
}

A query on the 1-indexed range [ql, qr] is performed using:

query(1, 1, N, ql, qr);

Point Updates

Here, j is a 1-indexed array position. Since a is stored as a normal 0-indexed C++ array, position j corresponds to a[j - 1].

Its corresponding leaf in the segment tree is j + N - 1.

void pointUpdate(int j, int v) {
    a[j - 1] = v;

    int idx = j + N - 1;
    seg[idx] = v;

    // reconstruct all ancestors
    for (int i = idx / 2; i > 0; i /= 2) {
        seg[i] = seg[i * 2] + seg[i * 2 + 1];
    }
}

Example Problem

Dynamic Range Minimum Queries

Dynamic Range Minimum Queries
CSES easy

Given array \(x\) of \(n\) elements and \(q\) queries. Each query is one of two types:

  • “1 \(k\) \(u\)”: update the value at position \(k\) to \(u\).
  • “2 \(a\) \(b\)”: what is the minimum value in range [\(a\),\(b\)]?
Solution

We’ll simply make a segment tree for minimum and apply the queries and point updates directly to it. Since the tree is a minimum segment tree, there will be some differences from the previous snippets: instead of adding the values of two children, we take their minimum, and the neutral value used for padding and disjoint query ranges is INT_MAX instead of 0.

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

const int MAXN = 200000;
const int N = 262144;  // the first power of two that is at least MAXN

int seg[N * 2];
int a[MAXN];

int query(int id, int l, int r, int ql, int qr) {
    // check if disjoint
    if (ql > r || l > qr) {
        return INT_MAX;
    }
    // check if [ql, qr] fully covers [l, r]
    if (ql <= l && r <= qr) {
        return seg[id];
    }
    // recurse and merge
    int m = (l + r) / 2;
    return min(query(id * 2, l, m, ql, qr), query(id * 2 + 1, m + 1, r, ql, qr));
}

void pointUpdate(int j, int v) {
    a[j - 1] = v;

    int idx = j + N - 1;
    seg[idx] = v;

    // reconstruct all ancestors
    for (int i = idx / 2; i > 0; i /= 2) {
        seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
    }
}

int main() {
    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n; i++) {
        seg[i + N] = a[i];
    }

    for (int i = n + N; i < 2*N; i++) {
        seg[i] = INT_MAX;  // padded value depends on the segment tree
    }

    for (int i = N - 1; i > 0; i--) {
        seg[i] = min(seg[i * 2], seg[i * 2 + 1]);
    }

    while (q--) {
        int type;
        cin >> type;

        if (type == 1) {
            int k, u;
            cin >> k >> u;
            pointUpdate(k, u);
        } else {
            int ql, qr;
            cin >> ql >> qr;

            cout << query(1, 1, N, ql, qr) << "\n";
        }
    }
}