虽然说:“一般普及组集训不会讲线段树,所以即便听不懂,也没有什么关系。”
但是我们也必须学好。
线段树是快速的查找某一个节点在若干条线段中出现的次数,RMQ也常常使用线段树来实现。
线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,实际应用时一般还要开4N的数组以免越界,因此有时需要离散化让空间压缩。
—— 百度百科
eg1:《动态成绩查询》
一个班里有n名学生,他们的学号是1~n
起初,所有人的成绩都是0,有m次操作。
- 给x加分或者减分
- 给定l,r求区间和
数据范围是很经典的$10^{5}$。
建立一个树,根是1~n的区间和,左孩子和有孩子是1~mid和mid~n,叶子节点为单个学生。
给x加分即给x的所有父节点加分,这就是线段树。
我们使用堆式存储存下整个树。
虽然说是有10w个节点,但是我们不能只开10w,我们要开2的整次幂,且接近10w。而$2^17$可以满足条件。
我们定义w[]存储一个节点的值。
单点加
我们单点加可以从叶子节点开始加,叶子节点加完后直接/2来到父节点。
void pointAdd(int pos, int k) {
// 找到 pos 在 w[] 位于什么位置
int cur = SIZE + pos - 1; // 例如,1号同学位于 w[131072]
while(cur != 0) {
w[cur] += k;
cur = cur / 2;
}
}
区间求和
如果要查询的区间就在自己的管辖范围之内,直接返回即可。如果不在就交给自己的孩子节点去做。
// 查询 [queryLe, queryRt] 的区间和
// querySum 要返回所查的那些元素,落在 node 管辖区间里面的这部分的 sum
// querySum 只管 「node 管辖区间」与「查询区间」的交集元素,其余的不管
int querySum(int node, int fieldLe, int fieldRt, int queryLe, int queryRt) {
if(queryRt < fieldLe || fieldRt < queryLe)
return 0; // 查询区间的右端点比管辖区间的 l 还小,显然本次查询不关这个 node 的事
if(queryLe <= fieldLe && fieldRt <= queryRt)
return w[node]; // 查询区间完全覆盖掉了 node 的管辖区间,返回 w[node],即管辖区间的 sum
// 例如,查询 [1, 100],而管辖区间是 [9, 16]
// 那我显然直接返回 sum(9, 16)
// 现在,查询区间和管辖区间有交集,需要细化处理
int mid = (fieldLe + fieldRt) / 2;
// 由左儿子查询、右儿子查询,返回它们的和
// 左儿子会处理自己管辖区域内的 sum,右儿子同理
int sumLe = querySum(node*2, fieldLe, mid, queryLe, queryRt);
int sumRt = querySum(node*2+1, mid+1, fieldRt, queryLe, queryRt);
return sumLe + sumRt;
}
eg2RMQ:洛谷P1816《忠诚》
我们在给区间加的时候顺手统计最小值即可。
#include <bits/stdc++.h>
using namespace std;
int n, m; // n 个学生,m 次操作
void input() {
cin >> n >> m;
}
// 维护一个长度为 131072(i.e. 2^17)长度的序列
#define SIZE 131072
int w[SIZE * 2 + 5]; // w[x]: x结点所管辖区间的 sum
// w[1] 的管辖区间是 [1, 131072]
// w[2]: [1, 65536], w[3]: [65537, 131072]
// ...
// w[131072]: [1, 1], ....
// 给 pos 同学加 k 分
// 目前正在处理 node 结点,它的管辖区间是 [fieldLe, fieldRt]
void pointAdd(int node, int fieldLe, int fieldRt, int pos, int k) {
// 更新 node 管辖区域的 sum
w[node] += k;
// 如果已经处理到底层,则更新 w 之后直接返回
if(fieldLe == fieldRt) return;
// 还需要递归处理
// 左半块:编号是 node*2, 管辖区间 [fieldLe, mid]
// 右半块:编号是 node*2+1, 管辖区间 [mid+1, fieldRt]
int mid = (fieldLe + fieldRt) / 2;
// 例如:node 管辖区间是 [8, 16]
// mid = (8+16)/2 = 12,左半块的管辖区间是 [8, 12];右半块 [13, 16]
if(pos <= mid) // 如果 pos 落在左半块,则递归给左边半块
pointAdd(node*2, fieldLe, mid, pos, k);
else
pointAdd(node*2+1, mid+1, fieldRt, pos, k);
}
// 查询 [queryLe, queryRt] 的区间和
// querySum 要返回所查的那些元素,落在 node 管辖区间里面的这部分的 sum
// querySum 只管 「node 管辖区间」与「查询区间」的交集元素,其余的不管
int querySum(int node, int fieldLe, int fieldRt, int queryLe, int queryRt) {
if(queryRt < fieldLe || fieldRt < queryLe)
return 0; // 查询区间的右端点比管辖区间的 l 还小,显然本次查询不关这个 node 的事
if(queryLe <= fieldLe && fieldRt <= queryRt)
return w[node]; // 查询区间完全覆盖掉了 node 的管辖区间,返回 w[node],即管辖区间的 sum
// 例如,查询 [1, 100],而管辖区间是 [9, 16]
// 那我显然直接返回 sum(9, 16)
// 现在,查询区间和管辖区间有交集,需要细化处理
int mid = (fieldLe + fieldRt) / 2;
// 由左儿子查询、右儿子查询,返回它们的和
// 左儿子会处理自己管辖区域内的 sum,右儿子同理
int sumLe = querySum(node*2, fieldLe, mid, queryLe, queryRt);
int sumRt = querySum(node*2+1, mid+1, fieldRt, queryLe, queryRt);
return sumLe + sumRt;
}
void work() {
while(m--) {
int cmd, x, y;
cin >> cmd >> x >> y;
if(cmd == 1)
pointAdd(1, 1, SIZE, x, y); // 交给 1 号结点,其管辖区间是 [1, SIZE]
else
cout << querySum(1, 1, SIZE, x, y) << endl; // 交给 1 号点,1 号的管辖区间是全集
}
}
int main() {
input();
work();
return 0;
}
This post was written on July 27, 2022