线段树总结

发表于 | 阅读次数:
字数统计: 1,840 字

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。是一种可以进行寻找信息统计,支持查询和修改的一种高级数据结构.

有关于线段树的知识, 之前就计划进行一个线段树的知识总结, 现在抽时间进行一下总结:

像之前一样, 还是先总结一下线段树具有的一些性质:

  1. 线段树的每一个节点都表示一个区间
  2. 线段树具有唯一的根节点, 代表的区间是整个统计范围, 如[1, N]
  3. 线段树的每一个叶结点都代表一个长度为 1 的元区间, 如 [x,x]
  4. 对于每一个内部节点[l,r], 他的左子结点是[l, mid], 右字节点是[mid+1, r], 其中 mid = (l+r) / 2 (向下取整)

线段树中各节点的表示方法:

  1. 根结点的编号为1
  2. 编号为 x 的节点的左子结点的编号为 x 2 (x<<1), 右字节点的编号为 x 2 + 1 (x<<1|1)

这样我们就可以简单的用一个struct数组来保存一颗线段树. 当然, 这颗线段树的最后一层可能并不是连续的, 并没有填满. 最后一层产生了空余, 所以保存线段树的数组长度要不小于 4 倍的 N才能保证不会越界．

线段树的建树

线段树的基本用途是对序列进行维护,进行查询与修改指令,如果 我们给定一个长度为 N 的序列A, 我们就可以在区间 [1, N] 上建立一颗线段树, 线段树的二叉树结构可以很方便的从下向上传递信息, 以区间最大值为例, 记dat(l,r) 等于 dat(l,r) = max(dat(l, mid), dat(mid+1, r)).

下面的代码建立了一颗线段树并在每个节点上保存了对应区间的最大值:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
struct SegmentTree {
    int l, r;
    int dat;
}t[SIZE * 4]；//数组储存线段树

void build(int p, int l ,int r) {
	t[p].l = l, t[p].r = r;			//结点p代表区间[l,r]
    if (l == r) {t[p].dat = a[l]; return;} //叶结点
    int mid = (l+r) / 2;				   //折半
    build(p*2, l, mid);
    build(p*2+1, mid+1, r);
    t[p].dat = max(t[p*2].dat, t[p*2+1].dat); // 从下往上传递信息
}

build(1, 1, n);//调用入口

线段树的单点修改

单点修改是一条形如 “C x y” 的命令, 意思是将 A[x] 的值改为v. 在线段树中, 根节点是执行各种命令的入口. 我们需要从根节点出发, 利用二分查找的性质,找到叶结点,然后从下往上更新这个点和他的所有祖先结点上保存的信息, 时间复杂度O(logN);

1
2
3
4
5
6
7
8
9
void change(int p , int x, int v) {
    if (t[p].l == t[p].r) {t[p].dat == v; return ;} //找到叶结点
    int mid = (l+r) / 2;
    if (x <= mid) change(p*2, l, mid);	//x属于左半区间
    else change(p*2+1, mid+1, r);	//x属于右半区间
    t[p].dat = max(t[p*2].dat, t[p*2+1].dat);
}

change(1, x, v);//调用入口

线段树的区间查询:

线段树的区间查询指令是一条形如 “Q l r” 的指令, 作用是查询在区间内维护的信息, 我们还是以区间最大值为例, 它的实现方式是从根节点开始, 递归查找区间内的信息. 查询的过程如下:

  1. 若 [l, r ] 完全覆盖了当前节点代表的区间, 则立即回溯, 并且该结点的 dat 值为候选答案
  2. 若左子结点与 [l, r ] 有重叠的部分, 则递归访问左子结点
  3. 若右子结点与 [l, r ] 有重叠的部分, 则递归访问右字结点

代码如下:

1
2
3
4
5
6
7
8
9
10
int ask(int p, int l, int r) {
    if (l <= t[p].l && r >= t[p].r) return t[p].dat;//完全包含
    int mid = (r+l) / 2;
    int val = -(1<<30);
    if (l <= mid) val = max(val, ask(p*2, l, mid));// 左子结点有重叠
    if (r > mid) val = max(val, ask(P*2+1, mid+1, r));// 右子结点有重叠
    return val;
}

ans = ask(1, l, r);

可以证明该查询操作的时间复杂度是 O(2logN) = O(logN) 的.

延迟标记(lazy tag)

我们发现, 如果我们需要进行区间修改操作, 我们进行更新的结点会变得很多, 这时候, 操作的时间复杂度会上升到 O(N), 这是我们不能接受的, 这时候我们需要引入延迟标记这个东西, 如果一个节点被打上了延迟标记, 与此同时这个点它自身保存的信息应该已经被修改完毕

下面给出代码演示:

1
2
3
4
5
6
7
8
9
void spread(int p) {
    if (t[p].add) {
        t[p*2].dat +=  t[p].add;
        t[p*2+1].dat += t[p].add;
        t[p*2].add += t[p].add;
        t[p*2+1].add += t[p].add;
        t[p].add = 0;
    }
}

完整代码

下面给出线段树带延迟标记的完整代码, 这是一个解决数列中某一区间同时加上一个数, 或者查询数列中某一段区间中的所有数的和的功能:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
struct SegmentTree {
	int l,r;
	long long sum, add;
	#define l(x) tree[x].l
	#define r(x) tree[x].r
	#define add(x) tree[x].add
	#define sum(x) tree[x].sum
}tree[maxn << 2];
int a[maxn], n, m;

void build(int p, int l ,int r) {
	l(p) = l; r(p) = r;
	if (l == r) {sum(p) = a[l]; return;}
	int mid = (l+r)/2; 
	build(p*2, l, mid);
	build(p*2+1, mid+1, r);
	sum(p) = sum(p*2) + sum(p*2+1);
}

void spread(int p) {
	if (add(p)) {
		sum(p*2) += add(p)*(r(p*2)-l(p*2)+1);
		sum(p*2+1) += add(p)*(r(p*2+1)-l(p*2+1)+1);
		add(p*2) += add(p);
		add(p*2+1) += add(p);
		add(p) = 0;
	}
}

void change(int p, int l, int r, int d) {
	if (l <= l(p) && r >= r(p)) {
		sum(p) += (long long)d * (r(p)-l(p)+1);
		add(p) += d;
		return;
	}
	spread(p);
	int mid = (l(p)+r(p))/2;
	if (l <= mid) change(p*2, l, r, d);
	if (r > mid) change(p*2+1, l, r, d);
	sum(p) = sum(p*2) + sum(p*2+1);
}

long long ask(int p, int l ,int r) {
	if (l <= l(p) && r >= r(p))	return sum(p);
	spread(p);
	int mid = (l(p)+r(p))/2;
	long long val = 0;
	if (l <= mid) val += ask(p*2, l, r);
	if (r > mid) val += ask(p*2+1, l, r);
	return val;
}

线段树的扩展应用

由于我们知道线段树可以维护区间信息, 但是并不是所有的区间信息都可以用线段树来维护, 下面总结一下常用的线段树可以维护的信息:

  1. 区间最值(max or min)
  2. 区间和(sum)
  3. 最大公因数(gcd)
  4. 区间加减乘

这些信息都可以用线段树来维护, 接受在线操作, 可谓是一个不得不学习的数据结构, 线段树经常应用在一些比如说 DP 的优化或者什么地方, 需要引起重视啊.