Segment Tree
1. Introduction
- A data structure for maintaining information over intervals.
- It supports dynamic interval operations: point updates, range updates, and range queries.
- Every problem solvable with a Binary Indexed Tree can be solved with a segment tree; the converse is not always true.
2. Principle and Implementation
A segment tree is a binary tree that is complete at every level except, possibly, the lowest. Each node represents an interval, while the leaves represent individual elements. A parent is computed from its children, for example by summing them or taking their maximum.
As Figure 1 shows, the segment tree represents the array [10, 11, 12, 13, 14], with each parent equal to the sum of its children.
In a binary tree, the left child of node n is numbered 2n and the right child is numbered 2n+1.
2.1 Building the Tree
void build(int p, int pl, int pr) { // 当前节点标号，以及其对应区间
if(pl == pr) {
tree[p] = a[pl]; // 抵达最底层，赋值
return;
}
int mid = (pl + pr) / 2;
build(2*p, pl, mid);
build(2*p+1, mid+1, pr);
tree[p] = tree[2*p] + tree[2*p+1]; // 重要赋值语句
}
Use recursion starting from the root. Each call passes the current node number and its interval to the next level, so invoke it as follows.
build(1, 1, n);
Stop when the recursion reaches a leaf: its interval has length 1, so its left and right endpoints are equal. At that point, assign the leaf value.
Otherwise recurse into both children, passing their respective numbers and intervals.
The assignment to the current node follows the two recursive calls. When those calls return, both children have been computed, so their values can be combined.
2.2 Range Queries
// p是当前节点,[pl,pr]是对应区间,[l,r]为目标区间
int query(int p, int pl, int pr, int l, int r) {
if(pl >= l && pr <= r) return tree[p];
int mid = (pl + pr) / 2;
int sum = 0;
if(mid >= l) sum += query(2*p, pl, mid, l, r);
if(mid+1 <= r) sum += query(2*p+1, mid+1, pr, l, r);
return sum;
}
Queries also use recursion and search downward from the root. Invoke one as follows.
query(1, 1, n, l, r);
If the current node’s interval is contained in the target interval, there is no need to search further: return the node’s value directly. This is where a segment-tree range query saves time.
Continue recursively after checking the relationship between the current interval and the target interval; the two if statements do this. Here, mid is the midpoint of the current interval.
If l ≤ mid, the target overlaps interval [pl, mid], which must therefore be searched, as Figure 2 shows.
If mid < r, the target overlaps interval [mid+1, pr], which must therefore be searched, as Figure 3 shows.
2.3 Point Updates
// p为当前节点，[pl,pr]为当前对应区间，目标是将第x个元素加上k
void update(int p, int pl, int pr, int x, int k) {
if(pl == pr) {
tree[p] += k;
return ;
}
int mid = (pl + pr) / 2;
if(x <= mid) update(p*2, pl, mid, x, k);
if(x >= mid+1) update(p*2+1, mid+1, pr, x, k);
tree[p] = tree[p*2] + tree[p*2+1];
}
Fundamentally, a point update uses the same recursive structure as building the tree.
2.4 Range Updates and Lazy Propagation
Using point updates for a range update requires traversing every element in that interval, which is too expensive.
This is why we introduce lazy propagation: delay changing a node’s information. A range of length n can be represented by fewer than n segment-tree nodes t[i]. Store the update on those nodes rather than immediately applying it to every child; perform the actual propagation only when a tagged node is visited again.
Implement lazy propagation while searching the tree.
- Start searching from the root.
- When the current interval is a subset of the target interval, apply the range update to this node: t[p] += (pr - pl + 1) * k, and record tag[p] += k.
- As stated above, make the actual change only when a tagged node is visited again. Whenever a node is visited, check its tag. If present, pass the tag to both children and clear it at the current node.
- Then compare the intervals and recurse.
void update(int p, int pl, int pr, int l, int r, int k) {
if(pl >= l && pr <= r) { // 当前区间为目标区间的子集
tag[p] += k;
tree[p] += (pr - pl + 1) * k;
return ;
}
int mid = (pl + pr) / 2;
if(tag[p]) {
tag[2*p] += tag[p];
tag[2*p+1] += tag[p]; // 把标记传递给两个子节点
tree[2*p] += (mid - pl + 1) * tag[p];
tree[2*p+1] += (pr - mid) * tag[p]; // 修改两个子节点的值
tag[p] = 0;
}
if(l <= mid) update(p*2, pl, mid, l, r, k);
if(r >= mid+1) update(p*2+1, mid+1, pr, l, r, k); // 递归
tree[p] = tree[p*2] + tree[p*2+1];
}
For example, add 5 to every value in range [3,5] of the array 10,11,12,13,14, as Figure 4 shows.
- Starting at the root finds [3,3] and [4,5], corresponding to nodes 5 and 3. Tag those two nodes and update their values.
- The recursive calls then return through the upper levels and update their values, such as nodes 1, 2, and 3, by summing their two children.
After the update, the segment tree is as shown in Figure 5:
How is the deferred update reflected? At this point, information in nodes 6 and 7 has not yet been updated, even though they belong to [3,5]. They will be updated the next time they are visited.
For example, query interval [4,4].
- On reaching node 3, which represents [4,5], find that it has a tag.
- Pass the tag to its two children and update their values.
- Clear the tag at the current node.
Passing a tag to nodes 6 and 7 is unnecessary because they are leaves. The generic propagation procedure, however, applies the same rule to every visited tagged node, so the tag is still passed to nodes 6 and 7, as Figure 6 shows.
When using lazy propagation, the query code must also be changed.
int query(int p, int pl, int pr, int l, int r) {
if(pl >= l && pr <= r) return tree[p]; // 当前区间为目标区间的子集
int mid = (pl + pr) / 2;
if(tag[p]) {
tag[2*p] += tag[p];
tag[2*p+1] += tag[p]; // 传递标记给两个子节点
tree[2*p] += (mid - pl + 1) * tag[p];
tree[2*p+1] += (pr - mid) * tag[p]; // 修改两个子节点的值
tag[p] = 0;
}
int sum = 0;
if(mid >= l) sum += query(2*p, pl, mid, l, r);
if(mid+1 <= r) sum += query(2*p+1, mid+1, pr, l, r); // 递归
return sum;
}
3. Examples
Example 1: Luogu P2357
A straightforward template problem. Range updates and range queries require lazy propagation.
For a point update, treat it as a range whose two endpoints are the same.
Example 2: Luogu P2574
For a binary sequence of length n, an update flips 0 to 1 and 1 to 0; a query asks for the number of ones in a target interval.
Here, array t stores the sum for its interval, namely the number of ones.
For an update, t[x] is the number of ones in its interval. Flipping the interval changes it to t[x] = len - t[x].
For tag, flipping an interval twice cancels itself. Let tag[x] = 1 mean a flip is pending and tag[x] = 0 mean none is pending. On each update, use tag[x] = !tag[x].
Finally, note that the input is a string and should be handled accordingly.
//修改和查询的代码
void update_tag() {
tag[p*2] = !tag[p*2];
tag[p*2+1] = !tag[p*2+1]; // 不同之处
tree[2*p] = (mid - pl + 1) - tree[2*p];
tree[2*p+1] = (pr - mid) - tree[2*p+1]; // 不同之处
tag[p] = 0;
}
void update(int p, int pl, int pr, int l, int r) {
if(pl >= l && pr <= r) {
tag[p] = !tag[p]; // 不同之处
tree[p] = (pr - pl + 1) - tree[p]; // 不同之处
return ;
}
int mid = (pl + pr) / 2;
if(tag[p]) update_tag();
recursion1();
}
int query(int p, int pl, int pr, int l, int r) {
if(pl >= l && pr <= r) return tree[p];
if(tag[p]) update_tag();
recursion2();
}
Example 3: Luogu P1198
A simple variation: replace summation with taking the maximum.
Tommy Chen
If you have the same hobbies, you can contact me.
