【c++提高1】数据结构之线段树详解

大纲

1.线段树思想

2.普通线段树操作函数

3.存储线段树

4.普通线段树操作实现

5.线段树常见搭配方式

6.进阶线段树-乘法线段树

7.进阶线段树-根号线段树

8.线段树解决问题

1.线段树思想

$线段树定义$

$线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。而未优化的空间复杂度为2N，实际应用时一般还要开4N的数组以免越界，因此有时需要离散化让空间压缩。$

$线段树的思想是将一个区间[1,n]划分成两个区间：$
$[1,n/2]和[n/2+1,n]，接下来继续划分：$
$[1,n/4],[n/4+1,n/2]和[n/2+1,n/2+n/4-1],[n/2+n/4,n]$
…

$这个时候你就会发现划分出的每一个区间，就是一个树的节点，所有的区间构成了一棵树，它就称为线段树。$
$线段树是一个二叉树。$

$示例：n=8$

2.线段树操作函数

1.pushup函数

$将子节点的值传输到他们的父节点上，tr[p]表示的是p整棵子树的结果，所以子节点的计算结果就是整棵子树的结果，有点像前缀和的思想。$

2.pushdown

$如果父节点改变，相应的子节点也需要，pushdown函数就是实现将父节点改变信息的一个函数，也称为懒惰标记，就是给孩子节点传递信息。$

3.build

$比较核心的函数：将原来的整区间建立成线段树。就是实现线段树的建树过程，如上面的划分方式，是通过递归的方式不停划分两个区间，递归建立子节点(l,mid)和(mid+1,r)。$

4.modify

$修改函数，一般支持两种操作：单点修改，区间修改。分别需要使用函数pushup和pushdown辅助修改。单点修改的时候因为单点改变，所以所有祖先即改变，所以递归调用不停update(pushup+手动更新)。$

5.query

$查询函数，查询一段区间的结果，递归调用，找到答案所在位置，或者分解成多个目标求解，最后返回答案。$

3.存储线段树

1.线段树的儿子存储

$因为每一个节点都表示一个区间，显然不能用区间作为下标来存储左右儿子（有可能可以直接存左右儿子地址），所以可以给每一个节点编一个编号，设做儿子为当前节点编号\ast 2，左节点为当前节点编号\ast 2+1，常见的使用数组存储二叉树的方式。$
根节点的编号为1，接下来顺序编号即可。

2.线段树的节点信息存储
$定义一个结构体，里面存储改节点信息和当前这个节点所管辖的区间的左右端点。$

struct Tree{
	int val;
	int l,r;
} tr[maxm<<2];
1
2
3
4

结构体存储线段树，别忘了数组开4倍。

4.线段树函数实现

1.建树函数build
$递归建树。$
$怎样判断当前节点是叶子节点呢？$

$可以发现叶子节点肯定是不能划分了，所以它所管辖的区间长度一定是1。所以判断是否l,r是否相等即可。$

bool is_leaf(int l,int r){
	return l==r;
}
1
2
3

$如果当前节点是叶子节点，那么不需要建立左右节点，直接设置val即可。否则它的左右节点就是当前节点的左右端点，并且分别build(l,mid)并且build(mid+1,r)$
$建树后子节点已经有值了，用他们得出当前的节点即可。$

bool is_leaf(int l,int r){
	return l==r;
}
void build(int p,int l,int r){
	tr[p].l=l,tr[p].r=r;
	if(is_leaf(l,r)){
		tr[i].val=v[l];
		return;
	}
	int mid=l+r>>1;
	build(p<<1,l,mid),build(p<<1|1,mid+1,r);
	//tr[p]=f(tr[p<<1].val,tr[p<<1|1].val);
	pushup(p);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.查询函数query
$我们在查询函数也在第二节的时候讲过了大概的查询思路，接下来更详细的讲一下。$
2.1区间查询
$这是最初示范的一个线段树，以它为例。$
$比如查询[4,7]的时候首先进入区间[1,8]，发现[4,7]被完全包含在了[1,8]里，深度+1。$

$对于它的两个子节点[1,4]和[5,8]，发现4与[1,4]有交集，计算。[5,7]同。（计算方法：有交集的，没有完全包含，但是又包含，单独计算）$

$手动模拟每一次的决策，总结一下：$

1.如果当前查的区间在查询的区间里面，那么直接get它的val即可。
2.如果当前查的区间的左儿子和查询的区间有交集，那么直接查左儿子。
3.如果当前查的区间的右儿子和查询的区间有交集，那么直接查右儿子。

$情况4.但是如果当前查的区间跟查询区间没有关系，那么这个区间等于没有贡献return0即可。$

int query(int p,int l,int r){
	if(tr[p].l>=l&&tr[p].r<=r)return tr[p].val; //情况1
	if(tr[p].r<l||tr[p].l>r)return 0; //情况4 
	int s=0; //那么计算它的子节点query即可, 用s累加
	if(tr[p<<1].r>=l)s+=query(p<<1,l,r);
	if(tr[p<<1|1].l<=r)s+=query(p<<1|1,l,r);
	return s; //传输结果
}
1
2
3
4
5
6
7
8

2.2单点查询
$简单来说就是找到目标(index)的val值，所以通过决策+遍历实现：$

操作①: 每次选择一个包含目标的儿子节点，进行查。
重复操作①，如果遍历到了叶子节点，get它的val即可。

int mv,index;
void get_val(int p,int l,int r){
	if(l==r){
		//get();
		mv=tr[p].val; return;
	}
	int ls=p<<1,rs=p<<1|1,mid=l+r>>1;
	if(index>=tr[ls].l&&index<=tr[ls].r)get_val(ls,l,mid);
	if(index>=tr[rs].l&&index<=tr[rs].r)get_val(rs,mid+1,r);
}
1
2
3
4
5
6
7
8
9
10

3.修改函数modify
3.1单点修改
$就是实现a[index]+=k。$

$这个很好理解，首先需要找到目标点的位置（就如单点query(index)），接下来修改它即可。$
没问题了
$其实是有一个问题的：$
$因为线段树是一颗树，每一个节点都是由子节点构成的，一个节点改变，会导致它到根节点的路径上都改变。$
这个时候请跳转到pushup函数。

$从根节点开始，但是因为一个点修改，它到根节点的路径都+k，所以将一路上的所有点都+k即可，所以代码是：$

void modify(int p,int d,int k){
	if(tr[p].l==tr[p].r){
		//modify();
		tr[i].val+=k; return;
	}
	if(d<=tr[i<<1].r)modify(i<<1,d,k);
	else modify(i<<1|1,dis,k);
	//pushup();
	//tr[i].val=f(tr[i<<1].val,tr[i<<1|1].val);
	tr[i].val=tr[i<<1].val+tr[i<<1|1].val; return;
}
1
2
3
4
5
6
7
8
9
10
11

3.2区间修改
$实现将区间[l,r]+=k$

就是首先将真个包含的区间的val直接改变(+=k)，对于其他的零散的区间，如果有完整的区间，那么就使用整的区间，否则对于那些单个的元素直接修改。

void modify(int p,int l,int r,int k){
	if(tr[p].l>=l&&tr[p].r<=r){   //完全包含 
		tr[p].val+=k;
		return; 
	}
	int mid=tr[p].l+tr[p].r>>1;
	/*
		.决策.左右儿子 
	*/
	if(l<=mid)modify(p<<1,l,r,k);
	if(r>mid)modify(p<<1|1,l,r,k);
}
1
2
3
4
5
6
7
8
9
10
11
12

4.pushup
$在上面的代码中已经提到了pushup这个函数，是出现在modify函数的末尾。$
为什么要在末尾呢？因为能进到当前这个modify函数里一定哈没有找到目标的index所以要继续往下找，到了深度更深的层次，找到了的时候它是这条路径上的一份子，所以根据规则进行自己节点的val值修改。
$不需要给pushup专门定义一个函数。$
$pushdown也可以不定义，但是一般是定义一下比较好（因为代码有点长）$
5.pushdown
$pushdown一般用于区间修改+区间查询的线段树。$
$其中的pushdown，就是把自己的懒惰标记归零，并给自己的儿子加上，并让自己的儿子加上k\ast (r-l+1)。$

void pushdown(int i){
	if(tr[i].lz!=0){
		tr[i<<1].lz+=tr[i].lz;
        tr[i<<1|1].lz+=tr[i].lz;
        int mid=(tr[i].l+tr[i].r)/2;
        tr[i<<1].sum+=tr[i].lz*(mid-tr[i<<1].l+1);
        tr[i<<1|1].sum+=tr[i].lz*(tr[i<<1|1].r-mid);
        tr[i].lz=0;
	}
}
1
2
3
4
5
6
7
8
9
10

5.线段树常见搭配方式

$一般我写线段树函数的时候是打包一个namespace的，或者写成一个结构体都可以，至少包装起来。$

(1).单点修改&区间查询

太简单了

(2).区间修改&单点查询

模板

#include
#define FOR(x,y,z) for(int x=y,x_=z;x<=x_;x++)
#define DOR(x,y,z) for(int x=y,x_=z;x>=x_;x--)
#define ll long long
using namespace std;
void read(int& x){
	char c;x=0;
	int f=1;
	while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
	do x=(x<<3)+(x<<1)+(c^48);
	while(c=getchar(),c>='0'&&c<='9');
	x*=f;
}
void write(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+48);
}
const int maxn=5e5+10;
int n,m,s,t,T,a[maxn];
namespace Seg{
	struct Node{
		int l,r; int val;
	}tr[maxn<<2];
	void build(int p,int l,int r){
		tr[p]={l,r,0}; //初始化
		if(l==r){      //叶子节点没有子节点 
			tr[p].val=a[l]; //直接赋值 
			return;
		}
		int mid=l+r>>1;
		build(p<<1,l,mid),build(p<<1|1,mid+1,r);
		//建立子节点 
	}
	void modify(int p,int l,int r,int k){
		if(tr[p].l>=l&&tr[p].r<=r){  //一个路径都要加 
			tr[p].val+=k;
			return;
		}
		int mid=tr[p].l+tr[p].r>>1;   
		if(l<=mid)modify(p<<1,l,r,k);
		if(r>mid)modify(p<<1|1,l,r,k);
		//决策左右儿子 
	}
	void query(int p,int index){
//	void get_()
		T+=tr[p].val;
		if(tr[p].l==tr[p].r)return; //子节点 
		int mid=tr[p].l+tr[p].r>>1;
		if(index<=mid)query(p<<1,index);
		else query(p<<1|1,index);
	}
}
int main(){
	read(n),read(m);
	FOR(i,1,n)read(a[i]);
	Seg:: build(1,1,n); //建树
	FOR(i,1,m){         //操作 
		int F; read(F);
		if(F==1){
			int t,x,y; read(t),read(x),read(y);
			Seg:: modify(1,t,x,y);
		}else{
			T=0;
			int x; read(x);
			Seg:: query(1,x);
			write(T),putchar('\n');
		}
	}
}

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

6.进阶线段树-乘法线段树

$如果一个线段树只包含乘法运算，把那些pushdown(laze{r}_{t}age)啥的都改成乘就行了。$
$假设改变一下，包含加法和乘法，那么可不是这么简单就可以解决了。$

当传递懒惰标记的时候，因为有乘和加，所以lazer_tage要判断乘和加的顺序，需要处理一下

这里的懒惰标记就分为plz(plus_lazer_tage)和mlz(mul_lazer_tage)。

mul_lazer_tage很简单，直接乘父节点即可。
plus_lazer_tage：plus_lazer_tage(i)*mul_lazer_tage(fa(i))+plus_lazer_tage(fa(i))
1
2

$pushdown代码：$

void pushdown(long long i){
    long long k1=tree[i].mlz,k2=tree[i].plz;
    tree[i<<1].sum=(tree[i<<1].sum*k1+k2*(tree[i<<1].r-tree[i<<1].l+1))%p;
    tree[i<<1|1].sum=(tree[i<<1|1].sum*k1+k2*(tree[i<<1|1].r-tree[i<<1|1].l+1))%p;
    tree[i<<1].mlz=(tree[i<<1].mlz*k1)%p;
    tree[i<<1|1].mlz=(tree[i<<1|1].mlz*k1)%p;
    tree[i<<1].plz=(tree[i<<1].plz*k1+k2)%p;
    tree[i<<1|1].plz=(tree[i<<1|1].plz*k1+k2)%p;
    tree[i].plz=0;
    tree[i].mlz=1;
    return;
}

1
2
3
4
5
6
7
8
9
10
11
12
13

7.根号线段树

$对于每个区间，维护它的最大值和最小值，然后每次修改时，如果这个区间的最大值根号和最小值的根号一样，说明这个区间整体根号不会产生误差，就直接修改$

其中，lazy_tage把除法当成减法，记录的是这个区间里每个元素减去的值。

$附赠根号线段树修改函数代码：$

void Sqrt(int i,int l,int r){
    if(tr[i].l>=l&&tr[i].r<=r&&(tr[i].minn-(long long)sqrt(tr[i].minn))==(tr[i].maxx-(long long)sqrt(tr[i].maxx))){
        long long u=tr[i].minn-(long long)sqrt(tr[i].minn);
        tr[i].lz+=u;
        tr[i].sum-=(tr[i].r-tr[i].l+1)*u;
        tr[i].minn-=u;
        tr[i].maxx-=u;
        return ;
    }
    if(tr[i].r<l||tr[i].l>r)return;
    push_down(i);
    if(tr[i<<1].r>=l)Sqrt(i<<1,l,r);
    if(tr[i<<1|1].l<=r)Sqrt(i<<1|1,l,r);
    tr[i].sum=tr[i<<1].sum+tr[i<<1|1].sum;
    tr[i].minn=min(tr[i<<1].minn,tr[i<<1|1].minn);
    tr[i].maxx=max(tr[i<<1].maxx,tr[i<<1|1].maxx);
    return;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

8.线段树解决问题

最大公约数也具有合并性，比如：

$接下来直接线段树的加法当成gcd即可，modify还是一样的，只不过update节点的时候一样，改一下gcd。$

#include
#define FOR(x,y,z) for(int x=y,x_=z;x<=x_;x++)
#define DOR(x,y,z) for(int x=y,x_=z;x>=x_;x--)
#define ll long long
using namespace std;
void read(ll& x){
	char c;x=0;
	int f=1;
	while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
	do x=(x<<3)+(x<<1)+(c^48);
	while(c=getchar(),c>='0'&&c<='9');
	x*=f;
}
void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);
	putchar(x%10+48);
}
const int maxn=5e5+10,maxl=5;
ll n,m; ll a[maxn];
struct Node{
	int l,r;
	ll val,d;
}tr[maxn<<2];
ll gcd(ll a,ll b){
	return b?gcd(b,a%b):a;
}
void pushup(Node& u,Node& l,Node& r){
	u.val=l.val+r.val,u.d=gcd(l.d,r.d);
}
void build(int u,int l,int r){
	if(l==r)tr[u]={l,r,a[r]-a[r-1],a[r]-a[r-1]};
	else{
		tr[u].l=l,tr[u].r=r;
		int mid=l+r>>1; build(u<<1,l,mid),build(u<<1|1,mid+1,r);
		pushup(tr[u],tr[u<<1],tr[u<<1|1]);
	}
}
void modify(int u,int x,ll vals){
	if(tr[u].l==x&&tr[u].r==x)tr[u]={x,x,tr[u].val+vals,tr[u].val+vals};
	else{
		int mid=tr[u].l+tr[u].r>>1;
		if(x<=mid)modify(u<<1,x,vals);
		else modify(u<<1|1,x,vals);
		pushup(tr[u],tr[u<<1],tr[u<<1|1]);
	}
}
Node query(int u,int l,int r){
	if(tr[u].l>=l&&tr[u].r<=r)return tr[u];
	else{
		int mid=tr[u].l+tr[u].r>>1;
		if(r<=mid)return query(u<<1,l,r);
		else if(l>mid)return query(u<<1|1,l,r);
		else{
			Node lt=query(u<<1,l,r),rt=query(u<<1|1,l,r),Tr;
			pushup(Tr,lt,rt); return Tr;
		}
	}
}
int main(){
	read(n),read(m);
	FOR(i,1,n)read(a[i]);
	build(1,1,n);
	int l,r; ll d;
	char q[maxl];
	FOR(i,1,m){
		scanf("%s%d%d",q,&l,&r);
		if(*q=='Q'){
			Node lt=query(1,1,l),rt;
			rt={0,0,0,0};
			if(l+1<=r)rt=query(1,l+1,r);
			write(abs(gcd(lt.val,rt.d))),putchar('\n');
		}else{
			read(d);
			modify(1,l,d); if(r+1<=n)modify(1,r+1,d *-1);
		}
	}
}

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
75
76
77
78
79