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
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:
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
Nleaf nodes, the total number of nodes is2N - 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
nelements andnis not a power of two, we pad the array with additional elements so that the number of leaf nodesNbecomes 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
nelements, because the next power of two is strictly less than2n. Therefore, at mostn - 1padding 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:
idis the index of the current node.lis the beginning of the interval covered by the current node.ris the end of the interval covered by the current node.qlis the beginning of the query range.qris the end of the query range.
All of l, r, ql, and qr are 1-indexed positions.
The function works as follows:
If
[ql, qr]and[l, r]are completely disjoint, discard the current node, as it does not contribute to the query.If
[ql, qr]completely covers[l, r], return the value stored at the current node.Otherwise, split the range at the midpoint
m = (l + r) / 2and 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]areseg[2 * i]andseg[2 * i + 1]. seg[0]is unused.
Positions used by queries and updates are also 1-indexed. Therefore:
- array position
jcorresponds toa[j - 1]; - array position
jcorresponds to segment-tree leafseg[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
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";
}
}
}