I was so much older then, I'm younger than that now.

P5494 【模板】线段树分裂

LawrenceSivan · 2021-5-25 · 次阅读

刚写了线段树分裂的板子。

线段树分裂

前置知识

1.权值线段树

有一个很好的博客可以看看：传送门

2.动态开点线段树：传送门

3.线段树合并：传送门

4.主席树：传送门

简介

线段树分裂，顾名思义就是将线段树分裂开。为了维护线段树合并所维护的可重集，我们需要将权值线段树中前 $k$ 小的数和其余数分在两颗权值线段树上进行维护。

具体操作

其实很简单，线段树分裂是线段树合并的逆操作。对于待分裂区域与其他区域的公有节点，复制一份；对于独有节点，直接拿过来挂上去；最后记得 pushup。

其实和主席树是有很高相似度的。

int split(int rt,int l,int r,int ql,int qr){
	int o=++tot;
	
	if(ql==l&&qr==r){
		st[o]=st[rt];
		st[rt].v=ls(rt)=rs(rt)=0;
		return o;
	}
	
	int mid=(l+r)>>1;
	
	if(qr<=mid){
		ls(o)=split(ls(rt),l,mid,ql,qr);
	}else if(ql>mid){
		rs(o)=split(rs(rt),mid+1,r,ql,qr);
	}else{
		ls(o)=split(ls(rt),l,mid,ql,mid);
		rs(o)=split(rs(rt),mid+1,r,mid+1,qr);
	}
	
	push_up(rt);push_up(o);
	return o;
}

~~然后这玩意就讲完了~~

这么说其实权值线段树的操作啥的几乎就都搞定了，再结合别的东西就可以把权值线段树~~放在手里把玩了~~运用得得心应手了。

复杂度分析

单点修改和区间修改

和普通线段树是一样的，都是 $O(logn)$.

找第 k 小

每层只会访问 $1$ 个节点，时间复杂度为 $O(logn)$.

线段树合并

仅当两颗线段树在相同的节点都有值时，合并才需要花费时间，否则可以直接返回有值的一边. $O(nlogn)$

这玩意复杂度确实很玄学，大家的说法也不太一样，于是我摘取了几位大佬的说法：

@gxy001:显然，我们每次只会访问重合节点，那么单次合并的时间复杂度就可以认为是较小树的节点个数，那么显然，多次合并的总复杂度为总点数级别，$O(nlogn)$

注：不能简单的认为其复杂度为单次合并的最坏复杂度乘询问次数。感性理解，在本题中，显然我们可以花费一次询问使树的节点加一条链，让合并的复杂度增大，但也会失去一次进行线段树合并的机会，这样就保证了其总复杂度不会过高。

@chenxinyang2006:

仅当两颗线段树在相同的节点都有值时，合并才需要花费时间，否则可以直接返回有值的一边

也就是说，合并一次，总节点数量减少1

一操作会在新线段树上，增加 $logn$ 个节点

三操作会增加一条链的节点，也是 $logn$ 个

所以总节点数不超过 $n+mlogn$，合并总复杂度不超过 $n+mlogn$

线段树分裂

我们可以看到，这个操作访问的节点和区间查询是一致的，复制边缘节点，直接拿走完整节点。时间复杂度 $O(logn)$

之后就是本题：

本题：

对于每个操作我们分着看：

操作零

就是分裂了：

int split(int rt,int l,int r,int ql,int qr){
	int o=++tot;
	
	if(ql==l&&qr==r){
		st[o]=st[rt];
		st[rt].v=ls(rt)=rs(rt)=0;
		return o;
	}
	
	int mid=(l+r)>>1;
	
	if(qr<=mid){
		ls(o)=split(ls(rt),l,mid,ql,qr);
	}else if(ql>mid){
		rs(o)=split(rs(rt),mid+1,r,ql,qr);
	}else{
		ls(o)=split(ls(rt),l,mid,ql,mid);
		rs(o)=split(rs(rt),mid+1,r,mid+1,qr);
	}
	
	push_up(rt);push_up(o);
	return o;
}

操作一

合并两棵树即可：

int merge(int p,int q){
	if(!p||!q)return p|q;
	
	int rt=++tot;
	st[rt].v=st[p].v+st[q].v;
	ls(rt)=merge(ls(p),ls(q));
	rs(rt)=merge(rs(p),rs(q));
	
	return rt;
}

操作二

单点修改

void modify(int rt,int l,int r,int pos,int val){
	if(l==r){
		st[rt].v+=val;
		return;
	}
	
	int mid=(l+r)>>1;
	if(pos<=mid){
		if(ls(rt)==0)ls(rt)=++tot;
		modify(ls(rt),l,mid,pos,val);
	}
	else {
		if(rs(rt)==0)rs(rt)=++tot;
		modify(rs(rt),mid+1,r,pos,val);
	}
	
	push_up(rt);
}

操作三

区间查询

ll query(int rt,int l,int r,int ql,int qr){
	if(ql>r||qr<l)return 0;
	if(ql<=l&&qr>=r){
		return st[rt].v;
	}
	
	int mid=(l+r)>>1;
	return query(ls(rt),l,mid,ql,qr)+query(rs(rt),mid+1,r,ql,qr);
}

操作四

查找第 $k$ 小，直接线段树上二分就行了

int kth(int rt,int l,int r,int k){
	if(l==r)return l;
	
	int mid=(l+r)>>1;
	if(st[ls(rt)].v>=k)return kth(ls(rt),l,mid,k);
	else return kth(rs(rt),mid+1,r,k-st[ls(rt)].v);
}

~~这么来看这题没啥技术含量，充其量就是学了个分裂函数~~

CODE

//#define LawrenceSivan

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define re register
const int maxn=2e5+5;
#define INF 0x3f3f3f3f

#define ls(x) st[x].l
#define rs(x) st[x].r

int n,m,tot,op,p,c=1;
int root[maxn];

ll a[maxn];

struct SegmentTree{
	ll v;
	int l,r;
}st[maxn<<6];

inline void push_up(int rt){
	st[rt].v=st[ls(rt)].v+st[rs(rt)].v;
}

int build(int l,int r){
	int rt=++tot;
	if(l==r){
		st[rt].v=a[l];
		return rt;
	}
	
	int mid=(l+r)>>1;
	ls(rt)=build(l,mid);
	rs(rt)=build(mid+1,r);
	
	push_up(rt);
	return rt;
}

int split(int rt,int l,int r,int ql,int qr){
	int o=++tot;
	
	if(ql==l&&qr==r){
		st[o]=st[rt];
		st[rt].v=ls(rt)=rs(rt)=0;
		return o;
	}
	
	int mid=(l+r)>>1;
	
	if(qr<=mid){
		ls(o)=split(ls(rt),l,mid,ql,qr);
	}else if(ql>mid){
		rs(o)=split(rs(rt),mid+1,r,ql,qr);
	}else{
		ls(o)=split(ls(rt),l,mid,ql,mid);
		rs(o)=split(rs(rt),mid+1,r,mid+1,qr);
	}
	
	push_up(rt);push_up(o);
	return o;
}

int merge(int p,int q){
	if(!p||!q)return p|q;
	
	int rt=++tot;
	st[rt].v=st[p].v+st[q].v;
	ls(rt)=merge(ls(p),ls(q));
	rs(rt)=merge(rs(p),rs(q));
	
	return rt;
}

void modify(int rt,int l,int r,int pos,int val){
	if(l==r){
		st[rt].v+=val;
		return;
	}
	
	int mid=(l+r)>>1;
	if(pos<=mid){
		if(ls(rt)==0)ls(rt)=++tot;
		modify(ls(rt),l,mid,pos,val);
	}
	else {
		if(rs(rt)==0)rs(rt)=++tot;
		modify(rs(rt),mid+1,r,pos,val);
	}
	
	push_up(rt);
}

ll query(int rt,int l,int r,int ql,int qr){
	if(ql>r||qr<l)return 0;
	if(ql<=l&&qr>=r){
		return st[rt].v;
	}
	
	int mid=(l+r)>>1;
	return query(ls(rt),l,mid,ql,qr)+query(rs(rt),mid+1,r,ql,qr);
}

int kth(int rt,int l,int r,int k){
	if(l==r)return l;
	
	int mid=(l+r)>>1;
	if(st[ls(rt)].v>=k)return kth(ls(rt),l,mid,k);
	else return kth(rs(rt),mid+1,r,k-st[ls(rt)].v);
}

inline ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^48);ch=getchar();}
    return x*f;
}

int main(){
#ifdef LawrenceSivan
    freopen("aa.in","r",stdin);
    freopen("aa.out","w",stdout);
#endif
	n=read();m=read();
	for(re int i=1;i<=n;i++){
		a[i]=read();
	}
	
	root[1]=build(1,n);
	
	for(re int i=1;i<=m;i++){
		op=read();p=read();
		if(op==0){
			int x=read(),y=read();
			root[++c]=split(root[p],1,n,x,y);
		}
		if(op==1){
			int x=read();
			root[p]=merge(root[p],root[x]);
		}
		if(op==2){
			int x=read(),y=read();
			modify(root[p],1,n,y,x);
		}
		if(op==3){
			int x=read(),y=read();
			printf("%lld\n",query(root[p],1,n,x,y));
		}
		if(op==4){
			ll k=read();
			if(query(root[p],1,n,1,n)<k)printf("-1\n");
			else printf("%d\n",kth(root[p],1,n,k));
		}
	}


	return 0;
}

替罪羊树学习笔记

P5490 【模板】扫描线

Author

LawrenceSivan

载入天数...载入时分秒...

LawrenceSivan

© 2021 hexo-sakura