首页 > 其他分享 >树套树

树套树

时间：2024-02-25 22:37:07浏览次数：34  
标签：return 树套 rs int res sum ls

树套树

树状数组，（动态开点线段树），平衡树

二逼平衡树

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

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

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

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

  4. 查询
    在区间内的前驱（前驱定义为小于
    ，且最大的数）

  5. 查询 \(k\) 在区间内的后继（后继定义为大于 \(k\)，且最小的数）

  • 区间问题

  • 前驱后继

使用线段树处理区间，每个区间维护平衡树 \(O(N\log^2 N+M\log^3 N)\)

树状数组套主席树 \(O((N+M)\log^2 N)\)

两种数据需要开两个结构体

拆到两个数据结构结合起来，取他们的优点

平衡树天然动态开点

#include<bits/stdc++.h>
using namespace std;
const int N=50010;
const int V=1e8;
int n,m;
#define INF 0x3f3f3f3f
int tot;
constexpr int L1=16,L2=27; 
struct SEG_Node{
	int ls,rs,sum;
	#define lc t[p].ls
	#define rc t[p].rs
	#define mid (L+R>>1)
}t[N*L1*L2];
int mknode(){
	++tot;
	return tot;
}
int a[N];
struct SEG{
	int rt;
	void pushup(int p){
		t[p].sum = t[lc].sum+t[rc].sum;
	}
	void modify(int &p,int L,int R,int x,int v){
		if(!p)p=mknode();
		if(L==R){
			t[p].sum += v;
			return;
		}
		if(x<=mid)modify(lc,L,mid,x,v);
		else modify(rc,mid+1,R,x,v);
		pushup(p);
	}
};
struct BIT{
	SEG c[N];
	#define lowbit(x) ((x)&-(x))
	void change(int x,int v,int k){
		if(x==0)return;
		for(int i=x;i<=n;i+=lowbit(i))
			c[i].modify(c[i].rt,0,V,v,k);
	}
	void find(int x,vector<int> &a){
		for(;x;x-=lowbit(x))a.emplace_back(c[x].rt);
	}
}bit;
int lsum(vector<int> a,vector<int> b){
	int res=0;//可能一个节点会变空
	for(auto x:a)if(x&&t[x].ls)res -= t[t[x].ls].sum;
	for(auto x:b)if(x&&t[x].ls)res += t[t[x].ls].sum;
	return res;
}
int rsum(vector<int> a,vector<int> b){
	int res=0;//可能一个节点会变空
	for(auto x:a)if(x&&t[x].rs)res -= t[t[x].rs].sum;
	for(auto x:b)if(x&&t[x].rs)res += t[t[x].rs].sum;
	return res;
}
void goL(vector<int> &a,vector<int> &b){
	for(int i=0;i<a.size();++i)if(a[i])a[i]=t[a[i]].ls;
	for(int i=0;i<b.size();++i)if(b[i])b[i]=t[b[i]].ls;
}
void goR(vector<int> &a,vector<int> &b){
	for(int i=0;i<a.size();++i)if(a[i])a[i]=t[a[i]].rs;
	for(int i=0;i<b.size();++i)if(b[i])b[i]=t[b[i]].rs;
}
int krank(int l,int r,int k){
	vector<int> a,b;
	a.clear();a.shrink_to_fit();
	b.clear();b.shrink_to_fit();
	bit.find(l-1,a);//当前的节点
	bit.find(r,b);//当前的节点
	int L=0,R=V;
	int res=1;
	while(L<=R){
		if(L==R)return res;
		if(k>mid)res += lsum(a,b);
		if(k<=mid)goL(a,b),R=mid;
		else goR(a,b),L=mid+1;
	}
}
int kth(int l,int r,int k){
	vector<int> a,b;
	a.clear();a.shrink_to_fit();
	b.clear();b.shrink_to_fit();
	bit.find(l-1,a);//当前的节点
	bit.find(r,b);//当前的节点
	int L=0,R=V;
	int res=0;
	while(L<=R){
		if(L==R)return L;
		int tmp=lsum(a,b);
		if(k<=tmp)R=mid,goL(a,b);
		else L=mid+1,k-=tmp,goR(a,b);
	}
}
int pre(int l,int r,int k){
	int rk=krank(l,r,k);
	return rk==1?-2147483647:kth(l,r,rk-1);
}
int suf(int l,int r,int k){
	int rk=krank(l,r,k+1);
	return rk==r-l+2?2147483647:kth(l,r,rk);
}
int main(){
	ios::sync_with_stdio(0); 
	cin>>n>>m;
	for(int i=1;i<=n;++i){
		cin>>a[i];
		bit.change(i,a[i],1);
	}
	for(int i=1;i<=m;++i){
		int opt;cin>>opt;
		if(opt==1){
			int l,r,k;
			cin>>l>>r>>k;
			printf("%d\n",krank(l,r,k));
		}else if(opt==2){
 			int l,r,k;
 			cin>>l>>r>>k;
 			printf("%d\n",kth(l,r,k));
		}else if(opt==3){
			int pos,k;cin>>pos>>k;
			bit.change(pos,a[pos],-1);
			a[pos]=k;
			bit.change(pos,a[pos],1);
		}else if(opt==4){
			int l,r,k;
			cin>>l>>r>>k;
			printf("%d\n",pre(l,r,k));
		}else{
			int l,r,k;
			cin>>l>>r>>k;
			printf("%d\n",suf(l,r,k));
		}
	}
	return 0;
}

K大数查询

权值线段树套线段树，线段树套权值线段树，都可以。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
int n,m;
const int N=5e4+10,L=32;
constexpr long long V=N+N;
struct Seg_Node{
	int ls,rs;
	ll sum,laz;
	#define lc(p) t[p].ls
	#define rc(p) t[p].rs
	#define mid (L+R>>1)
}t[N*L*L];
int tot;
struct Seg{
	int rt,ls,rs;
	int mknode(){
		return ++tot;
	}
	void pushup(int p){
		t[p].sum = t[lc(p)].sum+t[rc(p)].sum;
	}
	void op(int p,int v1,int v2){
		t[p].sum += v1;
		t[p].laz += v2;
	}
	void pushdown(int p,int L,int R){
		if(!t[p].ls)t[p].ls=mknode();
		if(!t[p].rs)t[p].rs=mknode();
		if(t[p].laz){
			op(lc(p),t[p].laz*(mid-L+1),t[p].laz);
			op(rc(p),t[p].laz*(R-mid),t[p].laz);
			t[p].laz=0;
		}
	}
	void modify(int &p,int L,int R,int l,int r,int v){
		if(!p)p=mknode();
		if(l<=L&&R<=r){
			op(p,(R-L+1)*v,v);
			return;
		}
		pushdown(p,L,R);
		if(l<=mid)modify(lc(p),L,mid,l,r,v);
		if(r>mid)modify(rc(p),mid+1,R,l,r,v);
		pushup(p);
	}
	ll query(int p,int L,int R,int l,int r){
		if(rt==0)return 0;
		if(l<=L&&R<=r)return t[p].sum;
		pushdown(p,L,R);
		ll res=0;
		if(l<=mid)res+=query(lc(p),L,mid,l,r); 
		if(r>mid)res+=query(rc(p),mid+1,R,l,r);
		return res;
	} 
}segt[N*L];
int TOT;
struct SEG{
	int rt;
	int mknode(){
		return ++TOT;
	}
	void change(int &p,int L,int R,int x,int l,int r){
		if(!p)p=mknode();
		segt[p].modify(segt[p].rt,1,n,l,r,1);
		// printf("rttrtrt %d %d\n",p,segt[p].rt);
		if(L==R)return;
		if(x<=mid)change(segt[p].ls,L,mid,x,l,r);
		else change(segt[p].rs,mid+1,R,x,l,r);
	}
	int query(int p,int L,int R,ll x,int l,int r){
		if(L==R)return L;
		int Rs=segt[p].rs;
		ll cntr=Rs?segt[Rs].query(segt[Rs].rt,1,n,l,r):0;
		if(x<=cntr)return query(segt[p].rs,mid+1,R,x,l,r);
		else return query(segt[p].ls,L,mid,x-cntr,l,r);
	}
}Seg;
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;++i){
		int opt,l,r;ll c;
		cin>>opt>>l>>r>>c;
		if(opt==1)
			Seg.change(Seg.rt,0,V,c+n,l,r);
		else
			cout<<Seg.query(Seg.rt,0,V,c,l,r)-n<<'\n';
	}
	return 0;
}

C++语言技巧

使用结构体

思想总结

问题的解决使用树套树的前提下，可以有多种解决方式，多种数据结构的套也许都能解决问题，那么就要进行综合复杂度分析。

树套树的本质是利用多种数树据结构的优势，比如第一题，既使用BIT进行区间查询，又使用树桶实现BST功能

标签：return,树套,rs,int,res,sum,ls
From： https://www.cnblogs.com/life-of-a-libertine/p/18033230

相关文章

  • 树套树板子，但是带修莫队+值域分块
    \(\text{Link-LuoguBlog}\)原题传送门没啥重要的事情，就是终于过了这题非常开心，发现自己是莫队的时间戳部分写错了调了114514年我也只能说是十分趣味。以及今天深刻地认识到了带修莫队应该len=pow(n,0.66);。就是裸的带修莫队+值域分块，就不说了，直接放代码了昂。如果有人......
  • 树套树
    伪树套树CF19DPoints我们只关心最值而不是所有点的信息，所以不需要真的矩形查询对\(x\)建权值线段树，维护纵坐标最大值就能线段树二分求出询问矩形中最小的横坐标，再在这个横坐标上找最小纵坐标即可，可以在叶子上用set维护\(y\)实现。时间复杂度\(O(n\logn)\)......
  • 【树套树，LCT，出栈序】P4027 [NOI2007] 货币兑换
    其实是我Li-Chao-Tree哒！！考虑转移\(f_x=\minf_{anc}+(d_{x}-d_{anc})p_x+q_x\)其中\(anc\)为\(x\)的祖先，然后满足\(d_{anc}\geqd_{x}-li_{x})\)。考虑如果用权值线段树+带撤销的李超树可以维护\(li_{x}\)可以维护\(li_{x}<0\)的情况。但是这个题......
  • 【学习笔记】树套树
    所谓树套树，其本质是通过用树维护一组树的根，从而维护强悍的数据1线段树套平衡树线段树套#include<bits/stdc++.h>usingnamespacestd;#defineMAXN50005intseg[MAXN<<2];intamin=1000000,amax=0;structNode{ intval,rnd,siz; intch[2]; }t[MAXN*80];intt......
  • 【个人模板封装】树套树、高维数据结构
    前言这是我个人使用的一些模板封装，限于个人能力，可能存在诸多不足与漏洞，在未加测试直接使用前请务必小心谨慎。更新可能会滞后于我本地的文档，如有疑问或者催更之类的可以在评论区留言。全文模板测试均基于以下版本信息，请留意版本兼容问题。Windows,64bitG++(ISOC++20)stack......
  • 树套树——维护区间内权值信息的“重武器”
    Introduction树套树，顾名思义，就是将各类“树”据结构的节点换成“树”，以此解决一些问题。一般情况下，两层树分别维护区间信息和区间内权值的信息。而因为树套树极劣的空间复杂度和巨大的常数，经常需要使用动态开点和垃圾回收的方法降低空间复杂度，以及一定的卡常技巧（将较为短小......
  • [浅谈] 二维数据结构——树套树
    \(\color{purple}\text{Ⅰ.二维树状数组}\)\(\color{orange}\text{例一：P3372【模板】线段树1}\)$\color{green}\text{2023.1.1014:32}$回忆一下树状数组的区间修改......
  • 树套树
    线套线规定使用OI坐标系。（按我的代码习惯）竖着关于\(1\simn\)建一棵线段树，该线段树的每个节点都是一棵内层线段树，若该节点的管辖区间为\([L,R]\)，则该内层线段树......
  • 树套树做矩形加矩形求和。
    题目大意：有一个\(n\timesn\)的矩阵，每个位置上初始值都为\(0\)，\(q\)次操作，分为两种：1.把横坐标在\([x_1,x_2]\)范围内，纵坐标在\([y_1,y_2]\)范围内的所有数加上一......
  • 【YBT2023寒假Day7 C】查区间（线段树套线段树）
    查区间题目链接：YBT2023寒假Day7C题目大意给你一个序列，要你维护两种操作，区间取min和区间求第k小。思路关于区间求第k小，有一个方法，是树套树。外层线段树维护位......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99