树套树
这里主要介绍树状数组套权值线段树的方法，毕竟基本上所有的树套树题都能用这种方法解，并且时间复杂度都是 \(n\times (logn)^2\)。
思路
这里有一道例题。
【模板】树套树
题目描述
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
-
查询 \(k\) 在区间内的排名
-
查询区间内排名为 \(k\) 的值
-
修改某一位置上的数值
-
查询 \(k\) 在区间内的前驱（前驱定义为严格小于 \(x\)，且最大的数，若不存在输出
-2147483647） -
查询 \(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; -
操作五同理就是将小于改为大于即可。