关键词：
最近学了学树套树，做了几道模板题。
发现好像有点水
咳咳咳。
树套树，顾名思义，一个树套一个树。比如树状数组套平衡树，就是把树状数组的每一个结点作为一颗平衡树，线段树套权值线段树，就是一颗线段树，每一个结点都是一颗权值线段树。。。
如果有一个问题是要求一个区间([l,r])中比(x)小的数有多少个带单点修改(n<=50000)，可以用树状数组套平衡树解决，首先在每个点上建立平衡树，然后再拿树状数组维护起来，然后我们可以先求出区间([1,r])中有多少个比(x)小的数减去区间([1,l-1])中有多少个比(x)小的数，每一个([1,x])的区间我们用树状数组选出(log)颗平衡树，在每颗平衡树上找出比(x)小的最后加起来就行了。修改就在树状数组上对应的平衡树中删除插入就行了。这样每次询问的复杂度为(log^2n)。
下面看几道题：
P3380 【模板】二逼平衡树（树套树）
嗯，这题有很多做法。
首先可以用树状数组套平衡树做。
排名本质上就是有多少比(x)小的。
第k小二分答案然后查排名加一个(log)是(log^3n)的。
前趋后继就是求出树状数组每一个点的前驱后继然后取( extmax)或( extmin)就行。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<cstdlib>
using namespace std;
const int INF=1e8;
const int N=5e4+100;
int tot,rad[N*30],size[N*30],v[N*30],ch[N*30][2],root[N<<3],x,y,z,n,m,a[N];
struct tree
int l,r;
tr[N<<3];
int new_node(int x)
int now=++tot;
rad[now]=rand();size[now]=1;v[now]=x;
return now;
void update(int now)
size[now]=size[ch[now][0]]+size[ch[now][1]]+1;
int merge(int x,int y)
if(x==0||y==0)return x+y;
if(rad[x]>rad[y])
ch[x][1]=merge(ch[x][1],y);
update(x);
return x;
else
ch[y][0]=merge(x,ch[y][0]);
update(y);
return y;
void split(int &x,int &y,int now,int k)
if(now==0)x=y=0;
else
if(v[now]<=k)
x=now;
split(ch[x][1],y,ch[x][1],k);
else
y=now;
split(x,ch[y][0],ch[y][0],k);
update(now);
void ins(int now,int w)
split(x,y,root[now],w);
root[now]=merge(merge(x,new_node(w)),y);
void ins(int x,int w,int now)
ins(now,w);
if(tr[now].l==tr[now].r)return;
int mid=(tr[now].l+tr[now].r)>>1;
if(x>mid)ins(x,w,now*2+1);
else ins(x,w,now*2);
int rank(int now,int k)
split(x,y,root[now],k-1);
int w=size[x];
root[now]=merge(x,y);
return w;
int rank(int l,int r,int k,int now)
if(tr[now].l==l&&tr[now].r==r)
return rank(now,k);
int mid=(tr[now].l+tr[now].r)>>1;
if(l>mid)return rank(l,r,k,now*2+1);
else if(r<=mid)return rank(l,r,k,now*2);
else return rank(l,mid,k,now*2)+rank(mid+1,r,k,now*2+1);
void work(int l,int r,int k)
int L=0,R=INF,ans;
while(L<=R)
int mid=(L+R)>>1;
if(rank(l,r,mid,1)<k)
ans=mid;
L=mid+1;
else R=mid-1;
printf("%d
",ans);
void del(int now,int w)
split(x,z,root[now],w);
split(x,y,x,w-1);
y=merge(ch[y][0],ch[y][1]);
root[now]=merge(merge(x,y),z);
void del(int x,int w,int now)
del(now,w);
if(tr[now].l==tr[now].r)return;
int mid=(tr[now].l+tr[now].r)>>1;
if(x>mid)del(x,w,now*2+1);
else del(x,w,now*2);
int kth(int now,int k)
int l=ch[now][0];
if(size[l]>=k)return kth(l,k);
else if(size[l]+1==k)return v[now];
else return kth(ch[now][1],k-size[l]-1);
int pre(int now,int k)
int ans;
split(x,y,root[now],k-1);
if(size[x]==0)ans=-2147483647;
else ans=kth(x,size[x]);
root[now]=merge(x,y);
return ans;
int pre(int l,int r,int k,int now)
if(tr[now].l==l&&tr[now].r==r)
return pre(now,k);
int mid=(tr[now].l+tr[now].r)>>1;
if(l>mid)return pre(l,r,k,now*2+1);
else if(r<=mid)return pre(l,r,k,now*2);
else return max(pre(l,mid,k,now*2),pre(mid+1,r,k,now*2+1));
int suc(int now,int k)
int ans;
split(x,y,root[now],k);
if(size[y]==0)ans=2147483647;
else ans=kth(y,1);
root[now]=merge(x,y);
return ans;
int suc(int l,int r,int k,int now)
if(tr[now].l==l&&tr[now].r==r)
return suc(now,k);
int mid=(tr[now].l+tr[now].r)>>1;
if(l>mid)return suc(l,r,k,now*2+1);
else if(r<=mid)return suc(l,r,k,now*2);
else return min(suc(l,mid,k,now*2),suc(mid+1,r,k,now*2+1));
void build(int l,int r,int now)
tr[now].l=l;tr[now].r=r;
if(l==r)return;
int mid=(l+r)>>1;
build(l,mid,now*2);
build(mid+1,r,now*2+1);
int read()
int sum=0,f=1;char ch=getchar();
while(ch<‘0‘||ch>‘9‘)if(ch==‘-‘)f=-1;ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘)sum=sum*10+ch-‘0‘;ch=getchar();
return sum*f;
int main()
srand(time(NULL));
n=read();m=read();
build(1,n,1);
for(int i=1;i<=n;++i)ins(i,a[i]=read(),1);
while(m--)
int type=read(),l=read(),r=read();
if(type==1)
int k=read();
printf("%d
",rank(l,r,k,1)+1);
else if(type==2)
int k=read();
work(l,r,k);
else if(type==3)
del(l,a[l],1);
ins(l,a[l]=r,1);
else if(type==4)
int k=read();
printf("%d
",pre(l,r,k,1));
else
int k=read();
printf("%d
",suc(l,r,k,1));
return 0;
然后我还写了一个线段树套权值线段树。
这个对于求第k大可以换一种求法。
就是先找到区间对应的线段树的区间编号（其实就是对应的权值线段树的根的编号），拿一个数组存下来，然后在权值线段树上二分就行了。这样复杂度就变成了(log^2n)的了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=5e4+100;
int sum[15000000],ch[15000000][2],root[N<<6];
int cnt,tot,n,m,num,c[N],b[N<<6],a[N],l[N],r[N],x[N],type[N];
struct tree
int l,r;
tr[N<<6];
void build(int l,int r,int now)
tr[now].l=l;tr[now].r=r;
if(l==r)return;
int mid=(l+r)>>1;
build(l,mid,now*2);
build(mid+1,r,now*2+1);
void add(int l,int r,int w,int k,int &now)
if(now==0)
now=++cnt;
ch[now][0]=ch[now][1]=0;
sum[now]=0;
sum[now]+=k;
if(l==r)return;
int mid=(l+r)>>1;
if(w>mid)add(mid+1,r,w,k,ch[now][1]);
else add(l,mid,w,k,ch[now][0]);
void add(int x,int w,int k,int now)
add(1,tot,w,k,root[now]);
if(tr[now].l==tr[now].r)return;
int mid=(tr[now].l+tr[now].r)>>1;
if(x>mid)add(x,w,k,now*2+1);
else add(x,w,k,now*2);
int check(int l,int r,int L,int R,int &now)
if(L>R)return 0;
if(now==0)
now=++cnt;
ch[now][0]=ch[now][1]=0;
sum[now]=0;
if(sum[now]==0)return 0;
if(l==L&&r==R)return sum[now];
int mid=(l+r)>>1;
if(L>mid)return check(mid+1,r,L,R,ch[now][1]);
else if(R<=mid)return check(l,mid,L,R,ch[now][0]);
else return check(l,mid,L,mid,ch[now][0])+check(mid+1,r,mid+1,R,ch[now][1]);
int rank(int l,int r,int k,int now)
if(tr[now].l==l&&tr[now].r==r)return check(1,tot,1,k-1,root[now]);
int mid=(tr[now].l+tr[now].r)>>1;
if(l>mid)return rank(l,r,k,now*2+1);
else if(r<=mid)return rank(l,r,k,now*2);
else return rank(l,mid,k,now*2)+rank(mid+1,r,k,now*2+1);
void find(int l,int r,int now)
if(tr[now].l==l&&tr[now].r==r)
c[++num]=root[now];
return;
int mid=(tr[now].l+tr[now].r)>>1;
if(l>mid)find(l,r,now*2+1);
else if(r<=mid)find(l,r,now*2);
else find(l,mid,now*2),find(mid+1,r,now*2+1);
int kth(int l,int r,int k)
num=0;
find(l,r,1);
int L=1,R=tot;
while(L!=R)
int tmp=0,mid=(L+R)>>1;
for(int i=1;i<=num;i++)tmp+=sum[ch[c[i]][0]];
if(tmp>=k)
R=mid;
for(int i=1;i<=num;i++)c[i]=ch[c[i]][0];
else
L=mid+1;k-=tmp;
for(int i=1;i<=num;i++)c[i]=ch[c[i]][1];
return L;
int kth(int l,int r,int k,int now)
if(l==r)return l;
int mid=(l+r)>>1;
if(sum[ch[now][0]]>=k)return kth(l,mid,k,ch[now][0]);
else return kth(mid+1,r,k-sum[ch[now][0]],ch[now][1]);
int pre(int now,int k)
if(now==0)return 0;
int tmp=check(1,tot,1,k-1,now);
if(tmp==0)return 0;
else return kth(1,tot,tmp,now);
int pre(int l,int r,int k,int now)
if(tr[now].l==l&&tr[now].r==r)return pre(root[now],k);
int mid=(tr[now].l+tr[now].r)>>1;
if(l>mid)return pre(l,r,k,now*2+1);
else if(r<=mid)return pre(l,r,k,now*2);
else return max(pre(l,mid,k,now*2),pre(mid+1,r,k,now*2+1));
int suc(int now,int k)
if(now==0)return tot+1;
int tmp=check(1,tot,k+1,tot,now);
if(tmp==0)return tot+1;
else return kth(1,tot,check(1,tot,1,k,now)+1,now);
int suc(int l,int r,int k,int now)
if(tr[now].l==l&&tr[now].r==r)return suc(root[now],k);
int mid=(tr[now].l+tr[now].r)>>1;
if(l>mid)return suc(l,r,k,now*2+1);
else if(r<=mid)return suc(l,r,k,now*2);
else return min(suc(l,mid,k,now*2),suc(mid+1,r,k,now*2+1));
int read()
int sum=0,f=1;char ch=getchar();
while(ch<‘0‘||ch>‘9‘)if(ch==‘-‘)f=-1;ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘)sum=sum*10+ch-‘0‘;ch=getchar();
return sum*f;
int main()
n=read();m=read();
build(1,n,1);
for(int i=1;i<=n;i++)a[i]=read(),b[++tot]=a[i];
for(int i=1;i<=m;i++)
type[i]=read(),l[i]=read(),r[i]=read();
if(type[i]==3)b[++tot]=r[i];
else
x[i]=read();
if(type[i]!=2)b[++tot]=x[i];
sort(b+1,b+1+tot);
tot=unique(b+1,b+1+tot)-b-1;
b[0]=-2147483647;b[tot+1]=2147483647;
for(int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+1+tot,a[i])-b;
add(i,a[i],1,1);
for(int i=1;i<=m;i++)
if(type[i]==3)r[i]=lower_bound(b+1,b+1+tot,r[i])-b;
else if(type[i]!=2)x[i]=lower_bound(b+1,b+1+tot,x[i])-b;
for(int i=1;i<=m;i++)
if(type[i]==1)printf("%d
",rank(l[i],r[i],x[i],1)+1);
else if(type[i]==2)printf("%d
",b[kth(l[i],r[i],x[i])]);
else if(type[i]==3)add(l[i],a[l[i]],-1,1),add(l[i],a[l[i]]=r[i],1,1);
else if(type[i]==4)printf("%d
",b[pre(l[i],r[i],x[i],1)]);
else if(type[i]==5)printf("%d
",b[suc(l[i],r[i],x[i],1)]);
return 0;
还有一种树状数组套权值线段树的方法，利用了k小的可减性。优化了常数和代码量。
但是我没写。。。
树套树乱讲的代码(代码片段)
树套树乱讲的代码由于部分代码的完成时间较早所以码风可能有些差异，敬请谅解。动态区间Kth题面整体二分题解#include<cstdio>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>usingnamespacestd;constintN=10005 查看详情
树套树浅谈(代码片段)
今天来说一下线段树套Splay。顺便我也来重新敲一遍模板。首先，明确一下Splay套线段树用来处理什么问题。它可以支持：插入x，删除x，单点修改，查询x在区间[l,r]的排名，查询区间[l,r]中排名为k的数，以及一个数在区间[l,r]中... 查看详情
uvalive-6709树套树(代码片段)
...法：暴力可过，建n颗线段树暴力更新，但是正解应该是树套树，树套树需要注意的是当建树或修改时pushup操作不能直接搞，要先判断是不是外面层的叶子节点，如果是直接修改，如果不是，应该是从外面层的对应子节点更新过... 查看详情
hdu4819mosaic树套树(代码片段)
...点变成这个矩形中最大值和最小值的平均数思路很显然的树套树啊就是一开始傻逼了没想到怎么去维护这个东西其实很简单对于每个内层树，如果属于外层树的叶子节点，那么可以直接暴力更新，复杂度(O(log(n)))voidmodify_y(intt,intl... 查看详情
「题解」树套树tree(代码片段)
本文将同步发布于：洛谷博客；csdn；博客园；简书。题目题目描述给你一个\\(n\\)个点的小树（正常的树），给你一个\\(m\\)个点的大树，大树的节点是一棵小树，大树的边是跨越了两棵小树之间的边，\\(q\\)次询问，求树上距离... 查看详情
hdu6096树套树(代码片段)
思路：网上的题解有AC自动机的，有trie树的，还有（乱搞？）的 首先把输入的那n个串按照字典序排序，把n个串翻转以后再按照字典序排序这样我们发现，查的前缀在字典序排序后是一段区间，查的后缀翻转一下在翻转后的... 查看详情
「luogu3380」模板二逼平衡树（树套树）(代码片段)
「luogu3380」【模板】二逼平衡树（树套树）传送门我写的树套树——线段树套平衡树。线段树上的每一个节点都是一棵( extFHQTreap)，然后我们就可以根据平衡树的基本操作以及线段树上区间信息可合并的性质来实现了，具体细节... 查看详情
4889:[tjoi2017]不勤劳的图书管理员树套树(代码片段)
...惯例的题面(Bzoj没有，洛谷找的):动态加权逆序对，一眼树套树。256MB内存，5e4范围，不虚不虚。首先把交换改成两个插入和两个删除。考虑插入和删除的贡献，就是统计前面比这个值大的数的数值和，数量和，后面比这个值小的... 查看详情
97:cf983e倍增+树套树(代码片段)
$des$一棵$n$个点的树，树上有$m$条双向的公交线路，每条公交线路都在两个节点之间沿最短路径往返。$q$次询问从一个点要到达另一个点，在只坐公交的情况下，至少需要坐几辆公交车；或者判断无法只坐公交到达。$n,m,q<=2 ime... 查看详情
树套树(代码片段)
历时三天终于打过了树套树 激动激动激动写个博客纪念一下 二逼平衡树~//luogu-judger-enable-o2#include<cstdio>#include<cstring>#include<algorithm>#include<iostream>#include<cmath>#include<stack>#include<queue>usingna... 查看详情
线段树树套树杭电ojluckandlove(代码片段)
博客主页:https://blog.csdn.net/qq_50285142欢迎点赞👍收藏✨关注❤留言📝如有错误，敬请指正🎈虽然生活很难，但我们也要一直走下去🎈题目链接思路：问题是要询问满足两个区间的最大缘分值，因为... 查看详情
二逼平衡树（树套树）(代码片段)
第一次写树套树，在一定帮助下学习，调码3h。用线段树套平衡树，对于区间内排名的查询可以解决了；//$O(log^2n)$对于查询区间排名为k的数，二分答案再判断；//$O(log^3n)$修改数值直接修改；//$O(log^2n)$前驱后继，线段树递归区间... 查看详情
二维线段树之树套树(代码片段)
1//poj1195二维线段树之树套树2//先确定横坐标所在的区间并记录该结点的编号p，然后再确定纵坐标所在的区间并记录该结点的编号cur，则tree[cur][p]为目标区间。3#include<cstdio>4#include<cstdlib>5#include<cstring>6#include<cmath&g... 查看详情
「模板」树套树
「模板」树套树<题目链接>线段树套SBT。有生以来写过的最长代码。虽然能过，但我删除SBT点的时候没回收内存！写了就RE！先放上来吧，回收内存调出来了再修改qwq。#include<algorithm>#include<climits>#include<cstdio>usin... 查看详情
洛谷p3380模板二逼平衡树（树套树，树状数组，线段树）(代码片段)
洛谷题目传送门emm。。。题目名写了个平衡树，但是这道题的理论复杂度最优解应该还是树状数组套值域线段树吧。就像dynamicranking那样（蒟蒻的Sol,放一个link骗访问量233）所有的值（包括初始a数组，操作1、3、4、5的k）全部先... 查看详情
模板二逼平衡树（树套树）(代码片段)
...但是码量绝对是很大的一种方法居然控制在了6KB以内线段树套红黑树（逃这是一次前所未有的尝试因为线段树套平衡树求区间第(k)小复杂度是(mathrmO(log^3n))的所以速度比不上树状数组套线段树但是应该在线段树套平衡树的代码中... 查看详情
p3759[tjoi2017]不勤劳的图书管理员[树套树](代码片段)
树套树是什么啊我不知道/dk我只知道卡常数w//byIsaunoya#pragmaGCCoptimize(2)#pragmaGCCoptimize(3)#pragmaGCCoptimize("Ofast")#pragmaGCCoptimize("inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2,-ffast-math,-fsched-spec,unroll-loops,-falign-jumps,-falig... 查看详情
[luogup3157][cqoi2011]动态逆序对(树套树)(代码片段)
...在外面再套上一颗树。这就很shit了。你问我资磁不资磁树套树，我是不资磁的，树套树是暴力数据结构，我能资磁吗？很不幸，昨天现实狠狠地打了我一脸：时间不够开新坑的，不切题又浑身难受，找了半天题，还是把这道题... 查看详情