线段树合并与分裂略解

发表于 更新于 分类于

前置芝士

  • 动态开点线段树
  • 线段树的一般操作（建树、修改、查询等）

（线段树分裂与合并通常建立在一棵值域线段树上）

线段树合并

首先，线段树合并。

假设我们要将 $R$ 树合并到 $L$ 树上。

流程如下：

  1. 在两棵树上都递归到一个位置，如果 $L$ 树的该位置对应的节点 $u$ 为空，则返回 $R$ 树的 $u$，反之亦然；
  2. 如果两棵树都有 $u$ 节点，则将 $R_{u}$ 的信息加到 $L_{u}$ 上，删除 $R_{u}$（也可不删，但在一些毒瘤题里可能会被卡空间），返回。

代码如下：

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
int rt[1000],n;//rt[]是每棵树的根

struct node{
	int l=0,r=0,cn=0;
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define cn(x) tr[x].cn
}tr[N];

int merge(int p,int q,int l,int r){
	if(!p)return q;
	if(!q)return p;
	if(l==r){
		cn(p)+=cn(q);
		return p;
	}
	int mid=(l+r)>>1;
	l(p)=merge(l(p),l(q),l,mid);
	r(p)=merge(r(p),r(q),mid+1,r);
	cn(p)=cn(l(p))+cn(r(p));
	return p;
}

int main(){
	merge(rt[L],rt[R],1,n);
}

线段树分裂

线段树分裂是线段树合并的逆过程。

我们假设要把 $L$ 树从 $k$ 处分裂成 $L$ 树（和分裂前不一样）和 $R$ 树，即将原来 $L$ 树中小于等于 $k$ 的数放到新 $L$ 树中，大于 $k$ 的数放到 $R$ 树中。

流程如下：

  1. 到达一个节点 $L_{u}$，判断 $k$ 在 $L_{u}$ 的左子树中还是右子树中；
  2. 如果在左子树中，则直接将 $L_{u}$ 的右子树给 $R_{u}$，并将 $L_{u}$ 的右子树删除，递归进入左子树；
  3. 如果在右子树中，则左子树不动，递归进入右子树；
  4. 如果到达叶子结点，则将 $L$ 的该节点作为 $R$ 的节点。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void split(int p,int& q,int l,int r,int k){
	if(!p)return ;
	q=++tot;
	if(l==r){
		swap(cn(p),cn(q));
		return ;
	}
	int mid=(l+r)>>1;
	if(k<=mid)swap(r(p),r(q)),split(l(p),l(q),l,mid,k);
	else split(r(p),r(q),mid+1,r,k);
	cn(p)=cn(l(p))+cn(r(p));
	cn(q)=cn(l(q))+cn(r(q));
}

int main(){
	split(rt[L],rt[R],1,n,k);
}

例题

洛谷P5494。

将线段树的合并与分裂有机结合。

代码：

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define mp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define PII pair<int,int>
const int MOD=998244353;
const int N=10000002;
const int M=10000001;
using namespace std;
inline int read(){register char c=getchar();register int s=0,f=1;for(;!isdigit(c);c=getchar())if(c=='-')f=-1;for(;isdigit(c);c=getchar())s=(s<<3)+(s<<1)+c-'0';return s*f;}
int n,m;
int a[N];
int rt[N],tot,cnt;
struct node{
	int l=0,r=0,cn=0;
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define cn(x) tr[x].cn
}tr[N];
int build(int l,int r){
	int p=++tot;
	if(l==r){
		cn(p)=a[l];
		return p;
	}
	int mid=(l+r)>>1;
	l(p)=build(l,mid);
	r(p)=build(mid+1,r);
	cn(p)=cn(l(p))+cn(r(p));
	return p;
}
void add(int &p,int l,int r,int k,int x){
	if(!p)p=++tot;
	if(l==r){
		cn(p)+=x;
		return ;
	}
	int mid=(l+r)>>1;
	if(k<=mid)add(l(p),l,mid,k,x);
	else add(r(p),mid+1,r,k,x);
	cn(p)=cn(l(p))+cn(r(p));
}
int qcn(int p,int l,int r,int L,int R){
	if(L<=l&&r<=R){
		return cn(p);
	}
	int mid=(l+r)>>1;
	int ans=0;
	if(L<=mid)ans+=qcn(l(p),l,mid,L,R);
	if(R>mid)ans+=qcn(r(p),mid+1,r,L,R);
	return ans;
}
int qk(int p,int l,int r,int k){
	if(k>cn(p))return -1;
	if(l==r)return l;
	int mid=(l+r)>>1;
	if(k<=cn(l(p)))return qk(l(p),l,mid,k);
	else return qk(r(p),mid+1,r,k-cn(l(p)));
}
int merge(int p,int q,int l,int r){
	if(!p)return q;
	if(!q)return p;
	if(l==r){
		cn(p)+=cn(q);
		return p;
	}
	int mid=(l+r)>>1;
	l(p)=merge(l(p),l(q),l,mid);
	r(p)=merge(r(p),r(q),mid+1,r);
	cn(p)=cn(l(p))+cn(r(p));
	return p;
}
void split(int p,int& q,int l,int r,int k){
	if(!p)return ;
	q=++tot;
	if(l==r){
		swap(cn(p),cn(q));
		return ;
	}
	int mid=(l+r)>>1;
	if(k<=mid)swap(r(p),r(q)),split(l(p),l(q),l,mid,k);
	else split(r(p),r(q),mid+1,r,k);
	cn(p)=cn(l(p))+cn(r(p));
	cn(q)=cn(l(q))+cn(r(q));
}
signed main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	rt[++cnt]=build(1,n);
	while(m--){
		int t=read(),p=read(),x=read();
		if(t==0){
			int y=read();
			int tmp=0;
			split(rt[p],tmp,1,n,y+1);
			split(rt[p],rt[++cnt],1,n,x);
			merge(rt[p],tmp,1,n);
		}
		else if(t==1){
			merge(rt[p],rt[x],1,n);
		}
		else if(t==2){
			int y=read();
			add(rt[p],1,n,y,x);
		}
		else if(t==3){
			int y=read();
			printf("%lld\n",qcn(rt[p],1,n,x,y));
		}
		else {
			printf("%lld\n",qk(rt[p],1,n,x));
		}
	}
	return 0;
}