线段树（懒标记）总结

This blog post is only available in Simplified Chinse.

线段树是非常基础的算法了……

线段树是一种二叉树，可视为树状数组的变种，最早出现在2001年，由程序竞赛选手发明。我们ZS老师说过：“所有可以用树状数组解决的题目都可以用线段树解决，但是部分线段数可以解决的题目却无法用树状数组解决。”由此可见线段树十分强大……

此资料结构实际应用用途不大，但由于其程式易于实作而被广泛应用于程式竞赛当中。其用途是在 $O(\log N)$ 查询一个指定区间内的资讯，并可在同样的时间复杂度支援更新等操作。 ——维基百科

例题

先来看看洛谷上的线段树模版题：【模板】线段树 1

题目描述

如题，已知一个数列，你需要进行下面两种操作： 1.将某区间每一个数加上x 2.求出某区间每一个数的和

输入输出格式

输入格式：第一行包含两个整数N、M，分别表示该数列数字的个数和操作的总个数。第二行包含N个用空格分隔的整数，其中第i个数字表示数列第i项的初始值。接下来M行每行包含3或4个整数，表示一个操作，具体如下：操作1：格式：1 x y k 含义：将区间[x,y]内每个数加上k 操作2：格式：2 x y 含义：输出区间[x,y]内每个数的和

输出格式：输出包含若干行整数，即为所有操作2的结果。

输入输出样例

输入样例

输出样例

11
8
20

说明

时空限制：1000ms,128M 数据规模：对于30%的数据：N<=8，M<=10 对于70%的数据：N<=1000，M<=10000 对于100%的数据：N<=100000，M<=100000 （数据已经过加强^_^，保证在int64/long long数据范围内）样例说明：

线段树的定义和构造

线段树（Segment Tree）是一个平衡的二叉树，所有叶子到根的距离最多只差1。令整个区间的长度为N，则其有N个叶节点，每个叶节点代表一个单位区间，每个内部结点代表的区间为其两个儿子代表区间的联集。

翻译成人话就是：线段树是个二叉树，每个节点表示一个区间（或许应该叫区间树……），叶节点代表的区间大小是1（即单位区间）。（以上面的例题为例）很容易理解，根据叶节点我们可以向上累计，对于每个非叶节点，很容易构造出其代表的区间内所有数字加和（以下称为“管辖区间和”（我自己起的名字……因为我觉得“管辖”这个词很高端……），用tree[x]表示x节点管辖区间和）（即每个点左右儿子代表区间和的加和）。这样向上构造，我们就可以造出一颗线段树。这就是build函数构造线段树的过程：

inline void build(int p,int tl,int tr){
	tag[p]=0;
	if (tl==tr) {tree[p]=a[tl];return;}
	int mid=((tr-tl)>>1)+tl;
	build((p<<1)  ,tl,mid  );
	build((p<<1)+1,mid+1,tr);
	tree[p]=tree[p<<1]+tree[(p<<1)+1];
}

区间更新与懒标记

如果没有区间更新，我们就用不到懒标记了，因为对于单点更新，直接向上推， $O(\log_2 N)$ 的时间内就可以得出结果。但是区间更新就十分麻烦：如果一个个单点进行更新，最高需要 $O(N* \log_2 N)$ ！显然很容易超时。懒标记（Lazy Tag）其实是对朴素的线段树的一个优化，可以让区间更新也达到 $O(\log_2 N)$ 级别。所以首先我们来认识一下懒标记：

懒标记

懒标记（Lazy Tag），也有的地方翻译成“延迟标记”（听起来高端……），就是指在更新一部分区间的时候，不更新这个区间里面的每个点，而是（懒惰地）把这个区间分割成很多个能用线段树上的点表示的区间（当然是分的区间越少越好，也就是说每个区间越大越好），只修正代表这个区间的点，再把这些区间标记下，下次如果要查询的区间与这个区间有交集并且没有包含这个区间，就说明需要“分割”这个区间，再将这个区间向下修正。这样时间复杂度就可以优化很多。

如何进行区间更新

刚才已经提到，如果要把区间[L,R]中所有元素加上delta，则只需要从线段树的根节点开始向下寻找，找到第一个被[L,R]包含的区间，就修正这个区间（注意“修正这个区间”只是增加这个区间和的标记和懒标记，不是把这个区间向下修正），然后继续向下找，直到找出来的一段段区间把[L,R]都覆盖了。

区间查询

区间查询和区间更新有点类似，假设要查询[L,R]，同样从根节点开始乡向下“分割”，不同之处在于：可能需要将刚才的懒标记用于向下修正。（具体见代码～）

完整代码（注释版）

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn=2000005;
int n,m;
long long a[maxn],tree[maxn],tag[maxn];
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
inline long long llread(){
	long long ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=(long long)-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*(long long)10+(long long)(ch-'0'),ch=getchar();
	return (long long)ret*f;
}
inline void build(int p,int tl,int tr){  //构造Segment Tree 
	tag[p]=0;
	if (tl==tr) {tree[p]=a[tl];return;}
	int mid=((tr-tl)>>1)+tl;
	build((p<<1)  ,tl,mid  );
	build((p<<1)+1,mid+1,tr);
	tree[p]=tree[p<<1]+tree[(p<<1)+1];
}
inline void push_down(int tl,int tr,int p){  //push_down函数负责向下传递，将存储的tag数组用于修正 
	int mid=((tr-tl)>>1)+tl;
	tree[p<<1]+=(long long)tag[p]*(mid-tl+1);  //只需要修正一对左右儿子，不需要一直传递到叶节点 
	tag[p<<1]+=tag[p];  //因为没有往下修正，所以要把儿子的tag累计上 
	tree[(p<<1)+1]+=(long long)tag[p]*(tr-mid);
	tag[(p<<1)+1]+=tag[p];
	tag[p]=0;
}
inline void update(int sl,int sr,int tl,int tr,long long delta,int p){
	if (sl<=tl&&sr>=tr){  //p管辖的区间在修改范围内 
		tree[p]+=delta*(long long)(tr-tl+1);
		tag[p]+=delta;  //tag数组记录剩下的未向下传递的，实现“lazy tag”
		return;
	}
	push_down(tl,tr,p);  //如果没有完全包含p管辖的区间，则说明应该向下“分割”，所以应该用tag数组先修正下面的tree[] 
	int mid=((tr-tl)>>1)+tl;  //分割[tl,tr]区间 
	if (sl<=mid) update(sl,sr,tl,mid,delta,p<<1);
	if (mid<sr)  update(sl,sr,mid+1,tr,delta,(p<<1)+1);
	tree[p]=tree[p<<1]+tree[(p<<1)+1];  //向上累计 
}
inline long long query(int sl,int sr,int tl,int tr,int p){  //查询操作 
	if (sl<=tl&&sr>=tr) return tree[p];  //如果完全包含p所管辖的区间则直接返回tree[p] 
	long long ret=0;  //否则就“分割” 
	push_down(tl,tr,p);  //先要把当前的tag用于修正下面两个儿子，这样才能保证下面query用到的tree[]是正确的 
	int mid=((tr-tl)>>1)+tl;
	if (sl<=mid) ret+=(long long)query(sl,sr,tl,mid,p<<1);
	if (mid<sr)  ret+=(long long)query(sl,sr,mid+1,tr,(p<<1)+1);
	return ret;
}
int main(){
	freopen("tree.in","r",stdin);
	freopen("tree.out","w",stdout);
	n=read();m=read();
	for (int i=1;i<=n;i++) a[i]=llread();
	build(1,1,n);
	for (int i=1;i<=m;i++){
		int c=read();
		if (c==1){
			int x=read(),y=read();
			long long z=llread();
			update(x,y,1,n,z,1);
		} else
		if (c==2){
			int x=read(),y=read();
			printf("%lld\n",query(x,y,1,n,1));
		}
	}
	return 0;
}

参考

https://www.luogu.org/blog/pks-LOVING/senior-data-structure-qian-tan-xian-duan-shu-segment-tree https://baike.baidu.com/item/%E7%BA%BF%E6%AE%B5%E6%A0%91/10983506 https://zh.wikipedia.org/zh/%E7%B7%9A%E6%AE%B5%E6%A8%B9_(%E5%84%B2%E5%AD%98%E5%8D%80%E9%96%93)

4/11/2018