线段树讲解一

Veröffentlicht am | in

概述

将区间不断二分划分所构成的树就是线段树。他的每个节点保存的是整个区间的某一段，如图所示：

线段树主要用于区间的动态查询和动态修改。

什么地方用得到线段树

父区间与子区间直接依赖

如果区间的信息可以由这个区间任意划分的两个不相交的子区间来构成，那么这就叫做父区间与子区间的直接依赖。
比如一段区间的和，可以随便将这个区间划分成两个不相交的子区间，然后由这两个区间的和来得到原区间的和：

如上图的$S$可以由$A$和$B$两个子区间构成。

不相交的区间信息独立

要使用线段树，还得保证不相交的两个区间的信息没有任何关系，如上图中，区间$A$的和与区间$B$的和没有任何关系。

分治的思想得到线段树

如果一个问题满足上述的性质，那么我们就可分治地来处理整个问题。对于我们要操作的每个区间，我们将其分成两半，由于左边和右边的信息是独立的，所以我们递归处理左右两边，然后将得到的信息合并回去。
那么假如我们早已保存了某个区间的信息，那么我们就不用一直分下去了。而保存这种信息的数据结构便是线段树。

时间和空间复杂度

由于我们的操作是分治的处理，所以无论是询问还是修改，时间复杂度都是$O(logn)$的，由于这是一棵完全二叉树，所以为了安全起见，我们应该会需要$O(4n)$的空间。

基本操作

首先讲解一下怎么单点更新某个值，然后询问区间和。
我们首先将线段树改造成满二叉树的形式，然后从上到下，从左向右给线段树的节点编号，则如果一个节点的编号是v，那么它的子节点就是v<<1和v<<1|1两个编号。

基本结构

1
2
3
4
5
6
7
8
9
//线段树
struct SegmentTree{
#define lchild L,m,v<<1
#define rchild m+1,R,v<<1|1
//每个节点
	struct Node{
		int sum;//当前节点保存的区间和
	}tree[4*MAX_N];
};

向上传递信息

1
2
3
void pushUp(int v){
	tree[v].sum=tree[v<<1].sum+tree[v<<1|1].sum;//父节点的信息由两个子节点来构成
}

构建线段树

要构建整个线段树，我们应该不断递归分治构建，在叶子节点的时候复制序列的信息

1
2
3
4
5
6
7
8
9
10
11
12
void build(int L=1,int R=N,int v=1){
	if(L==R){
		tree[v].sum=a[L];//a是原序列，这里表示走到了叶子节点
		return;
	}
	else{
		int m=(L+R)>>1;//找到中间的位置
		build(lchild);//处理左儿子
		build(rchild);//处理右儿子
	}
	pushUp(v);//将左右两个儿子的信息传上来
}

更新序列中某个位置的值

如果我们走到了叶子节点就直接修改，然后不断pushUp上去就好。

1
2
3
4
5
6
7
8
9
10
void update(int t,int x,int L=1,int R=N,int v=1){
	if(L==R){
		tree[v].sum=x;//走到叶子节点直接改
		return;
	}
	int m=(L+R)>>1;
	if(t<=m)update(t,x,lchild);//如果在左边，就更新左儿子
	else update(t,x,rchild);//如果在右边，就更新右儿子
	pushUp(v);//将左右两个儿子的信息传上来
}

查询一段区间的和

假设我们要查询[a,b]的和，如果当前查询区间已经覆盖了整个节点，我们就将这个节点的信息直接上传，否则就去查他的子节点。如下图：

在上图中，我们要查询[3,6]的区间和，我们就需要将区间分开去求解（红色），直到当前区间[L,R]被[3,6]完全覆盖（蓝色）

1
2
3
4
5
6
7
8
9
int query(int a,int b,int L=1,int R=N,int v=1){
	if(a<=L&&R<=b)//如果当前节点已经被[a,b]覆盖则直接返回值
		return tree[v].sum;
	int m=(L+R)>>1;
	int res=0;
	if(a<=m)res+=query(a,b,lchild);//如果查询区间和左儿子有交集，则查询左儿子
	if(b>m)res+=query(a,b,rchild);//如果查询区间和右儿子有交集，则查询右儿子
	return res;
}

完整的单点更新，区间查询和的代码：

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX_N 100005
using namespace std;
int a[MAX_N];
int N;
struct SegmentTree{
#define lchild L,m,v<<1
#define rchild m+1,R,v<<1|1
	struct Node{
		int sum;
	}tree[4*MAX_N];
	void pushUp(int v){
		tree[v].sum=tree[v<<1].sum+tree[v<<1|1].sum;
	}
	void build(int L=1,int R=N,int v=1){
		if(L==R){
			tree[v].sum=a[L];
			return;
		}
		else{
			int m=(L+R)>>1;
			build(lchild);
			build(rchild);
		}
		pushUp(v);
	}
	void update(int t,int x,int L=1,int R=N,int v=1){
		if(L==R){
			tree[v].sum=x;
			return;
		}
		int m=(L+R)>>1;
		if(t<=m)update(t,x,lchild);
		else update(t,x,rchild);
		pushUp(v);
	}
	int query(int a,int b,int L=1,int R=N,int v=1){
		if(a<=L&&R<=b)
			return tree[v].sum;
		int m=(L+R)>>1;
		int res=0;
		if(a<=m)res+=query(a,b,lchild);
		if(b>m)res+=query(a,b,rchild);
		return res;
	}
};
SegmentTree seg;
int M;
int main(){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++)
		scanf("%d",&a[i]);
	seg.build();
	while(M--){
		char op[2];
		int l,r;
		scanf("%s%d%d",op,&l,&r);
		if(op[0]=='Q')printf("%d\n",seg.query(l,r));
		else seg.update(l,r);
	}
	return 0;
}