线段树(以区间和为例)
在对区间进行操作时,例如区间合并,线段树是一个很好用的数据结构。
需要注意的是,对区间的操作应该要满足结合律,比如四则运算,异或等,否则不能使用线段树,具体原因在后续区间修改的代码中会进行说明。
概述
线段树的根节点是一个长区间,例如输入不超过N个的数,那么可以将根节点设为[1,N],它的左右子节点为均分父节点的两个区间,即左半区间和右半区间 [ 1 , ⌊ N + 1 2 ⌋ ] , [ ⌊ N + 1 2 ⌋ + 1 , N ] [1,\lfloor\frac{N+1}2\rfloor],[\lfloor\frac{N+1}2\rfloor+1,N] [1,⌊2N+1⌋],[⌊2N+1⌋+1,N],依次递归地建立,直到叶子节点,即区间 [ i , i ] [i,i] [i,i]。
除了区间外,我们还需要存储每个区间维护的值,这个依据需求来定,由于本文以区间求和为例,所以在本文中,这个值value为区间中的数之和,我们注意到,对于叶节点的值是容易的,即value=i即可,而父节点的值为子节点的值之和,显然这个过程需要从下到上的递归。
此外,最重要的一点是对区间的修改操作,不难注意到,如果我们想对区间 [ l , r ] [l,r] [l,r]修改,我们希望找到所有的节点 [ i , j ] [i,j] [i,j],其中 i ≥ l , r ≥ j i\ge l,r\ge j i≥l,r≥j,进行值的修改,这是一个从上到下的搜索。通过不断的对节点进行二分,是可以找到的,但不难发现,找到一对满足的节点,例如 [ l , m i d ] , [ m i d + 1 , r ] [l,mid],[mid+1,r] [l,mid],[mid+1,r]是很快的, O ( l o g 2 n ) O(log_2n) O(log2n),但我们如果想修改他们的子节点,就变为了 O ( n l o g 2 n ) O(nlog_2 n) O(nlog2n),这是一个比较大的时间了。
考虑优化的话,注意到我们更关注一个区间上的变化,例如我想查询 [ 1 , 4 ] [1,4] [1,4],那么我们只需要找到 [ 1 , 4 ] [1,4] [1,4]这个节点,或者是两个节点能拼凑成这样的节点即可,我们并不关注他的一系列子节点,例如 [ 2 , 3 ] [2,3] [2,3],这意味着,我们每次进行修改时,其实并不需要真的修改每一个节点,只需要搜索到恰好满足的节点进行修改后停下,做一个标记,代表这个区间是做过修改的。
这个标记被称为懒标记
,因为有了这个标记,我们不必修改它的子节点,当真正需要使用时,我们才将懒标记下放给子节点进行修改。
例如,在某次操作中,我们对区间 [ 1 , 4 ] [1,4] [1,4]中的每个元素都加了1,那么这个节点(或者是这两个节点),会进行修改,并使懒标记1,此时他们的子节点(例如叶节点1,2,3,4)值并没有修改;而随后,我们想对区间 [ 2 , 3 ] [2,3] [2,3]进行查询(区间和),在向下搜索的时候,我们需要将懒标记向下传递,使得子区间的值能够被正确修改。
简而言之,我们可以理解为,没使用这个区间,就不改,要用的时候再改,而懒标签就是累计的修改,这样我们可以节约大量时间,这也是精华所在。
综上,我们可以得到一个比较基本的线段树节点模板,即包含区间左右边界,维护的值,以及懒标签,其余属性可以根据需求自行添加。
例子1 区间求和(模板)
P3372 【模板】线段树 1 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题目描述
如题,已知一个数列,你需要进行下面两种操作:
- 将某区间每一个数加上 𝑘k。
- 求出某区间每一个数的和。
输入格式
第一行包含两个整数 𝑛,𝑚n,m,分别表示该数列数字的个数和操作的总个数。
第二行包含 𝑛n 个用空格分隔的整数,其中第 𝑖i 个数字表示数列第 𝑖i 项的初始值。
接下来 𝑚m 行每行包含 33 或 44 个整数,表示一个操作,具体如下:
1 x y k
:将区间 [𝑥,𝑦] 内每个数加上 𝑘k。2 x y
:输出区间 [𝑥,𝑦] 内每个数的和。
输出格式
输出包含若干行整数,即为所有操作 2 的结果。
结构体
struct SegTree {
int l, r;
long long value;//节点保存的值
long long tag;//懒标记
}t[MAX<<1+2];
建树
void build(int cur, int l, int r) {
t[cur].l = l;
t[cur].r = r;
if (l == r) {
t[cur].value = nums[l];//叶节点赋值,nums是输入的一系列数字
return;
}
int mid = l + r >> 1;
build(cur << 1, l, mid);
build(cur << 1 | 1, mid + 1, r);//递归地建左右子树
t[cur].value = t[cur << 1].value + t[cur << 1 | 1].value;//节点的值等于子节点值的和
}
建树过程是递归的,真正的赋值只发生在叶节点,父节点的值是两个子节点的值之和(可能会根据情况不同而有所改变)。此处我们不难发现,整个区间的值是由一个个叶子节点结合运算得来的,例如 value=1+2+3+4+5+6=(1+2+3)+(4+5+6)=(1+(2+3))+(4+(5+6))。如果这个运算不满足结合律,显然根据这个建树过程,得到的结果一定是错误的。
懒标记的传递
在向下查询的同时,将懒标记传递下去,并更改子节点的值(注意现处的节点值已更改过)
void spread(int cur) {
//懒标记的传递,将父区间的修改传递给自区间,本题中区间中的数加上懒标签
if (t[cur].tag) {
t[cur << 1].value += t[cur].tag * (t[cur << 1].r - t[cur << 1].l + 1);//加上k×区间长度
t[cur << 1 | 1].value += t[cur].tag * (t[cur << 1 | 1].r - t[cur << 1 | 1].l + 1);
t[cur << 1].tag += t[cur].tag;
t[cur << 1 | 1].tag += t[cur].tag;//将懒标记传递给子区间,注意是+=
t[cur].tag = 0;//清除父区间的懒标签
}
}
注意清除父区间的懒标签
区间修改
查询和修改是类似的,此处一起给出,注意在向下搜索前,一定要把懒标签传递下去后,再搜索,这个很重要。
void add(int cur, int left, int right, int adder) {
//对[left,right]区间+adder
if (left<=t[cur].l && right>=t[cur].r) {
//区间被完全覆盖,直接更改
t[cur].value += (long long)adder * (t[cur].r - t[cur].l + 1);
t[cur].tag += adder;//不要忘了更改懒标签
return;
}
spread(cur);//没有被完全覆盖,向下寻找被覆盖了的子区间,要把懒标记给传递下去
int mid = (t[cur].l + t[cur].r) >> 1;
if (left <= mid) add(cur << 1, left, right, adder);//更新区间的左边界在mid左边,则在左子区间找一下
if (right > mid) add(cur << 1 | 1, left, right, adder);//更新区间的右边界在mid右边,在右子区间找一下
t[cur].value = t[cur << 1].value + t[cur << 1 | 1].value;//最后回溯回来,更改父节点维护的值
return;
}
long long sum(int cur, int left, int right) {
//对[left,right]区间求和
if (left <= t[cur].l && right >= t[cur].r)
return t[cur].value;//覆盖区间,直接返回
spread(cur);//没有被完全覆盖,需要找子区间,则要传递懒标签
int mid = (t[cur].l + t[cur].r) >> 1;
long long ans = 0;
if (left <= mid) ans += sum(cur << 1, left, right);
if (right > mid) ans += sum(cur << 1 | 1, left, right);
return ans;//类似add
}
主函数
int main(){
int n,m;
cin >> n >>m;
for (int i = 1; i <= n; i++) {
cin >> nums[i];
}
build(1, 1, n);
for (int i = 1; i <= m; i++) {
int c, left, right, adder;
cin >> c;
if (c == 1) {
cin >> left>>right>>adder;
add(1, left, right, adder);
}
if (c == 2) {
cin >> left>>right;
cout << sum(1, left, right) << endl;
}
}
return 0;
}
例子2 开关
[P3870 TJOI2009] 开关 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
没什么区别,懒标记的传递甚至更简单了,给出部分代码。
void build(int cur, int l, int r) {
t[cur].l = l;
t[cur].r = r;
t[cur].tag = 0;
if (l == r) {
t[cur].value = 0;//灯是关着的
return;
}
int mid = l + r >> 1;
build(cur << 1, l, mid);
build(cur << 1 | 1, mid + 1, r);
t[cur].value = t[cur << 1].value + t[cur << 1 | 1].value;//其实就是0,但表示一下值的关系,即父区间灯亮的个数是子区间的和
}
void spread(int cur) {
//懒标记的传递,其实只有两个值,0和1,因为开关两次说明没变过
if (t[cur].tag) {
t[cur << 1].value = t[cur << 1].r - t[cur << 1].l + 1 - t[cur << 1].value;//总的灯数减去关之前亮起的
t[cur << 1 | 1].value = t[cur << 1 | 1].r - t[cur << 1 | 1].l + 1 - t[cur << 1 | 1].value;
t[cur << 1].tag ^= 1;//之前是0变为1,之前是1变为0
t[cur << 1 | 1].tag ^= 1;
t[cur].tag = 0;
}
return;
}
void change(int cur, int left, int right) {
if (left <= t[cur].l && right >= t[cur].r) {
t[cur].value = t[cur].r - t[cur].l + 1 - t[cur].value;
t[cur].tag ^= 1;
return;
}
spread(cur);
int mid = (t[cur].l + t[cur].r) >> 1;
if (left <= mid) change(cur << 1, left, right);
if (right > mid) change(cur << 1 | 1, left, right);
t[cur].value = t[cur << 1].value + t[cur << 1 | 1].value;
return;
}