个人中心
gpt4 book ai didi

树套树

转载 作者：撒哈拉 更新时间：2024-04-07 19:08:58 61 4
gpt4 key购买 nike

树套树

这里主要介绍树状数组套权值线段树的方法，毕竟基本上所有的树套树题都能用这种方法解，并且时间复杂度都是 \(n\times (logn)^2\).

思路

这里有一道例题.

【模板】树套树

题目描述

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作:

  1. 查询 \(k\) 在区间内的排名 。

  2. 查询区间内排名为 \(k\) 的值 。

  3. 修改某一位置上的数值 。

  4. 查询 \(k\) 在区间内的前驱（前驱定义为严格小于 \(x\)，且最大的数，若不存在输出 -2147483647） 。

  5. 查询 \(k\) 在区间内的后继（后继定义为严格大于 \(x\)，且最小的数，若不存在输出 2147483647） 。

输入格式

第一行两个数 \(n,m\)，表示长度为 \(n\) 的有序序列和 \(m\) 个操作.

第二行有 \(n\) 个数，表示有序序列.

下面有 \(m\) 行，\(opt\) 表示操作标号.

若 \(opt=1\)，则为操作 \(1\)，之后有三个数 \(l~r~k\)，表示查询 \(k\) 在区间 \([l,r]\) 的排名.

若 \(opt=2\)，则为操作 \(2\)，之后有三个数 \(l~r~k\)，表示查询区间 \([l,r]\) 内排名为 \(k\) 的数.

若 \(opt=3\)，则为操作 \(3\)，之后有两个数 \(pos~k\)，表示将 \(pos\) 位置的数修改为 \(k\).

若 \(opt=4\)，则为操作 \(4\)，之后有三个数 \(l~r~k\)，表示查询区间 \([l,r]\) 内 \(k\) 的前驱.

若 \(opt=5\)，则为操作 \(5\)，之后有三个数 \(l~r~k\)，表示查询区间 \([l,r]\) 内 \(k\) 的后继.

输出格式

对于操作 \(1,2,4,5\)，各输出一行，表示查询结果.

样例 #1

样例输入 #1

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

样例输出 #1

2
4
3
4
9

看完题目后可以发现这是一道树套树，然后下文主要讲解如何使用这棵树套树.

顾名而思义，就是用树状数组的方式来维护权值线段树（动态开点），我们对于上述的 \(5\) 个操作分别来看一下如何实现.

  • 操作 \(1\) 查询 \(l\sim r\) 中 \(k\) 的排名，我们会只放在权值线段树上的做法，这里就是会多维护 \(2\) 个数组，就是和普通的树状数组一样，将每一次的 \(l,r\) 都存下来，然后在查询中用 \(r\) 的总和减去 \(l\) 的即可，记住在往另一个地方递归时要更新这两个数组.

    int rk1(int l,int r,int k) {
	if(l==r) {
		return 1;
	}
	int mid=(l+r)/2,sum=false;
	rep(i,1,cs) sum-=tr[tr[s[i]].l].sum;//和普通的树状数组相同
	rep(i,1,cp) sum+=tr[tr[p[i]].l].sum; 
	if(mid>=k) {
		rep(i,1,cs) s[i]=tr[s[i]].l;//向那一边递归也要将 l,r 数组改一下
		rep(i,1,cp) p[i]=tr[p[i]].l;
		return rk1(l,mid,k);
	}else{
		rep(i,1,cs) s[i]=tr[s[i]].r;
		rep(i,1,cp) p[i]=tr[p[i]].r;
		return sum+rk1(mid+1,r,k);
	} 
}
l--;//用 r 的减去 l-1 的就为 l~r 中的
cs=cp=false;//清空
for(;l;l-=lowbit(l)) s[++cs]=rt[l];//与树状数组模板一样
for(;r;r-=lowbit(r)) p[++cp]=rt[r];

  • 对于操作二，其实和 \(1\) 的实现过程一样，就是在普通权值线段树上加上了 \(l,r\) 数组的改变而已.

    int Ans(int l,int r,int k) {
	if(l==r) return l;
	int mid=(l+r)>>1;
	int sum=false;
	rep(i,1,cs) sum-=tr[tr[s[i]].l].sum;//同理
	rep(i,1,cp) sum+=tr[tr[p[i]].l].sum;//同理
	if(k<=sum) {
		rep(i,1,cs) s[i]=tr[s[i]].l;//改变
		rep(i,1,cp) p[i]=tr[p[i]].l;
		return Ans(l,mid,k);
	}else {
		rep(i,1,cs) s[i]=tr[s[i]].r;//改变
		rep(i,1,cp) p[i]=tr[p[i]].r;
		return Ans(mid+1,r,k-sum);
    }
}
l--;//用 r 的减去 l-1 的就为 l~r 中的
cs=cp=false;//清空
for(;l;l-=lowbit(l)) s[++cs]=rt[l];//与树状数组模板一样
for(;r;r-=lowbit(r)) p[++cp]=rt[r];

  • 操作三是最简单的直接修改即可，这里可以直接结合树状数组的方式直接将每一个都 modify 一下即可.

    void modify(int &u,int l,int r,int k,int cnt) {
	if(!u) u=++idx;//动态开点
	tr[u].sum+=cnt;//加上
	if(l==r) return;
	int mid=(l+r)/2;
	if(mid>=k) modify(tr[u].l,l,mid,k,cnt);
	else modify(tr[u].r,mid+1,r,k,cnt);
}
in(l),in(k);
for(int i=l;i<=n;i+=lowbit(i)) modify(rt[i],0,Max,a[l],-1);//先减后加
a[l]=k;
for(int i=l;i<=n;i+=lowbit(i)) modify(rt[i],0,Max,a[l],1);

  • 操作四，这里我不会直接转移所以用了一下二分一下排名，直接看排名为 \(mid\) 的数是否小于 \(k\) 即可.

    in(l),in(r),in(k);
int L=1,R=r-l+1,res=false;
while(L<=R) {
	int mid=L+R>>1;
	cs=cp=false;
	for(int i=l-1;i;i-=lowbit(i)) s[++cs]=rt[i];
	for(int i=r;i;i-=lowbit(i)) p[++cp]=rt[i];
	if(Ans(0,Max,mid)<k) res=mid,L=mid+1;
	else R=mid-1;
}
if(!res) {
	cout<<"-2147483647\n";
	continue;
}
cs=cp=false;
for(int i=l-1;i;i-=lowbit(i)) s[++cs]=rt[i];
for(int i=r;i;i-=lowbit(i)) p[++cp]=rt[i];
cout<<Ans(0,Max,res)<<endl;

  • 操作五同理就是将小于改为大于即可.

总代码

#include <bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define rep1(i,x,y) for(register int i=x;i>=y;--i)
#define in(x) scanf("%d",&x)
#define ll long long
#define fire signed
#define il inline
il void print(int x) {
	if(x<0) putchar('-'),x=-x;
	if(x>=10) print(x/10);
	putchar(x%10+'0');
}
int T;
const int N=5e4+10;
struct node{
	int l,r;
	int sum;
}tr[N*2*16*16];
const int Max=1e8+1;
int n,m,idx;
int cp,cs;
int p[N],s[N];
void modify(int &u,int l,int r,int k,int cnt) {
	if(!u) u=++idx;
	tr[u].sum+=cnt;
	if(l==r) return;
	int mid=(l+r)/2;
	if(mid>=k) modify(tr[u].l,l,mid,k,cnt);
	else modify(tr[u].r,mid+1,r,k,cnt);
}
int rt[N],a[N];
int lowbit(int x) {
	return x&-x;
}
int rk(int l,int r,int k) {
	if(l==r) {
		int sum=false;
		rep(i,1,cs) sum-=tr[tr[s[i]].l].sum;
		rep(i,1,cp) sum+=tr[tr[p[i]].l].sum; 
		if(!sum) sum=1;
		return sum;
	}
	int mid=(l+r)/2,sum=false;
	rep(i,1,cs) sum-=tr[tr[s[i]].l].sum;
	rep(i,1,cp) sum+=tr[tr[p[i]].l].sum; 
	if(mid>=k) {
		rep(i,1,cs) s[i]=tr[s[i]].l;
		rep(i,1,cp) p[i]=tr[p[i]].l;
		return rk(l,mid,k);
	}else{
		rep(i,1,cs) s[i]=tr[s[i]].r;
		rep(i,1,cp) p[i]=tr[p[i]].r;
		return sum+rk(mid+1,r,k);
	} 
}
int rk2(int l,int r,int k) {
	if(l==r) {
		int sum=false;
		rep(i,1,cs) sum-=tr[tr[s[i]].l].sum;
		rep(i,1,cp) sum+=tr[tr[p[i]].l].sum;
		return sum;
	}
	int mid=(l+r)/2,sum=false;
	rep(i,1,cs) sum-=tr[tr[s[i]].l].sum;
	rep(i,1,cp) sum+=tr[tr[p[i]].l].sum; 
	if(mid>=k) {
		rep(i,1,cs) s[i]=tr[s[i]].l;
		rep(i,1,cp) p[i]=tr[p[i]].l;
		return rk2(l,mid,k);
	}else{
		rep(i,1,cs) s[i]=tr[s[i]].r;
		rep(i,1,cp) p[i]=tr[p[i]].r;
		return sum+rk2(mid+1,r,k);
	} 
}
int rk1(int l,int r,int k) {
	if(l==r) {
		return 1;
	}
	int mid=(l+r)/2,sum=false;
	rep(i,1,cs) sum-=tr[tr[s[i]].l].sum;
	rep(i,1,cp) sum+=tr[tr[p[i]].l].sum; 
	if(mid>=k) {
		rep(i,1,cs) s[i]=tr[s[i]].l;
		rep(i,1,cp) p[i]=tr[p[i]].l;
		return rk1(l,mid,k);
	}else{
		rep(i,1,cs) s[i]=tr[s[i]].r;
		rep(i,1,cp) p[i]=tr[p[i]].r;
		return sum+rk1(mid+1,r,k);
	} 
}
int Ans(int l,int r,int k) {
	if(l==r) return l;
	int mid=(l+r)>>1;
	int sum=false;
	rep(i,1,cs) sum-=tr[tr[s[i]].l].sum;
	rep(i,1,cp) sum+=tr[tr[p[i]].l].sum;
	if(k<=sum) {
		rep(i,1,cs) s[i]=tr[s[i]].l;
		rep(i,1,cp) p[i]=tr[p[i]].l;
		return Ans(l,mid,k);
	}else {
		rep(i,1,cs) s[i]=tr[s[i]].r;
		rep(i,1,cp) p[i]=tr[p[i]].r;
		return Ans(mid+1,r,k-sum);
	}
}
void solve() {
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	in(n),in(m);
	rep(i,1,n) {
		in(a[i]);
		for(int j=i;j<=n;j+=lowbit(j)) modify(rt[j],0,Max,a[i],1);
	}
	while(m--) {
		int opt;
		int l,r,k;
		in(opt);
		if(opt==1) {
			in(l),in(r),in(k);
			cs=cp=false;
			l--;
			for(;l;l-=lowbit(l)) s[++cs]=rt[l];
			for(;r;r-=lowbit(r)) p[++cp]=rt[r];
			cout<<rk1(0,Max,k)<<endl;
		}else if(opt==2){
			in(l),in(r),in(k);
			cs=cp=false;
			l--;
			for(;l;l-=lowbit(l)) s[++cs]=rt[l];
			for(;r;r-=lowbit(r)) p[++cp]=rt[r];
			cout<<Ans(0,Max,k)<<endl;
		}else if(opt==3) {
			in(l),in(k);
			for(int i=l;i<=n;i+=lowbit(i)) modify(rt[i],0,Max,a[l],-1);
			a[l]=k;
			for(int i=l;i<=n;i+=lowbit(i)) modify(rt[i],0,Max,a[l],1);
		}else if(opt==4) {
			in(l),in(r),in(k);
			int L=1,R=r-l+1,res=false;
			while(L<=R) {
				int mid=L+R>>1;
				cs=cp=false;
				for(int i=l-1;i;i-=lowbit(i)) s[++cs]=rt[i];
				for(int i=r;i;i-=lowbit(i)) p[++cp]=rt[i];
				if(Ans(0,Max,mid)<k) res=mid,L=mid+1;
				else R=mid-1;
			}
			if(!res) {
				cout<<"-2147483647\n";
				continue;
			}
			cs=cp=false;
			for(int i=l-1;i;i-=lowbit(i)) s[++cs]=rt[i];
			for(int i=r;i;i-=lowbit(i)) p[++cp]=rt[i];
			cout<<Ans(0,Max,res)<<endl;
		}else {
			in(l),in(r),in(k);
			int L=1,R=r-l+1,res=false;
			while(L<=R) {
				int mid=L+R>>1;
				cs=cp=false;
				for(int i=l-1;i;i-=lowbit(i)) s[++cs]=rt[i];
				for(int i=r;i;i-=lowbit(i)) p[++cp]=rt[i];
				if(Ans(0,Max,mid)>k) res=mid,R=mid-1;
				else L=mid+1;
			}
			if(res==0) cout<<"2147483647\n";
			else {
				cs=cp=false;
				for(int i=l-1;i;i-=lowbit(i)) s[++cs]=rt[i];
				for(int i=r;i;i-=lowbit(i)) p[++cp]=rt[i];
				cout<<Ans(0,Max,res)<<endl;
			}
		}
	}
	return;
}
fire main() {
	T=1;
	while(T--) {
		solve();
	}
	return false;
}

最后此篇关于树套树的文章就讲到这里了,如果你想了解更多关于树套树的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

61 4 0
文章推荐： K8s技术全景：架构、应用与优化
文章推荐： ArrayandSetworkprocess
文章推荐： 探索基于WebRTC的有感录屏技术开发流程
文章推荐： SpringBoot中bean的生命周期
撒哈拉
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com