定义

线段树是最常用的处理区间状态的数据结构之一，和树状数组类似。线段树可以在 $O(logN)$ 的复杂度内实现单点修改，区间修改，区间查询等操作。

基本结构

线段树就是对一段区间一直从中间断开，分成左儿子和右儿子。分别维护左儿子和右儿子，回朔的时候再维护这个父节点。从而这样一个区间就变成了一颗二叉树。

以下拿加法线段树举例

建树

因为是一颗完全二叉树，所以，若当前节点的编号为 O​ 可以让左儿子的编号为 o*2 ，右儿子的编号为 o*2+1 ，这样数组就不会冲突。

代码

(使用了 位运算 )

1
2
3
4
5
6
7
8
9
10
// o 为编号, t[o]: 线段树数组, a[l]: 原数组
void build(int o,int l,int r) {
	if(l==r) {
		t[o]=a[l];
		return;
	}
	int mid=(l+r)>>1;
	build(o<<1,l,mid),build(o<<1|1,mid+1,r);
	t[o]=t[o<<1]+t[o<<1|1]
}

修改

1. 单点修改

如果我们要修改一个点，那么所有包含这个点的区间都要被修改。易知复杂度是 $O(logN)$ 的。

代码
1
2
3
4
5
6
7
8
9
10
11
// 将 a[x] 修改为 y
void update(int o,int l,int r,int x,int y) {
	if(l==r) {
		t[o]=y;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) update1(o<<1,l,mid,x,y);
	else update1(o<<1|1,mid+1,r,x,y);
	t[o]=t[o<<1]+t[o<<1|1];
}
2. 区间修改

如果每次修改一个区间都下放到所有子区间并且更新包含这个区间的区间的话，复杂度就会承受不了了。这时候下放的就先“欠”着，等要用的时候再一起下放下去。这种优化就叫做 lazytag (懒标记) 。

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//下放
void pushdown(int o,int l,int r) {
	int mid=(l+r)>>1;
	lazy[o<<1]+=lazy[o];
	lazy[o<<1|1]+=lazy[o];
	t[o<<1]+=(mid-l+1)*lazy[o];
	t[o<<1|1]+=(r-mid)*lazy[o];
	lazy[o]=0;
}

// 将 [,ri] 全部改为 k
void modify(int o,int l,int r) {
	if(l>=li && r<=ri) {
		lazy[o]+=k;
		t[o]+=(r-l+1)*k;
		return;
	}
	pushdown(o,l,r);
	int mid=(l+r)>>1;
	if(li<=mid) modify(o<<1,l,mid);
	if(ri>mid) modify(o<<1|1,mid+1,r);
	t[o]=t[o<<1]+t[o<<1|1];
}

查询

查询一个区间的状态，如在这个情景下是「和」。

如查询区间 $[2,9]$ 就只需要查询这些区间返回就好了。

代码
1
2
3
4
5
6
7
8
9
10
11
12
// 查询 [li,ri] 的「和」
long long query(int o,int l,int r,int li,int ri) {
	if(l>=x && r<=y) {
		return t[o];
	}
	pushdown(o,l,r);
	int mid=(l+r)>>1;
	long long ret=0;
	if(li<=mid) ret+=query(o<<1,l,mid,li,ri);
	if(ri>mid) ret+=query(o<<1|1,mid+1,li,ri);
	return ret;
}

模板

线段树一：仅含区间加法的线段树 -> Links

线段树二：同时含有区间加法及区间乘法 -> Links


 Previous

OI 线段树

 Comments