这就是所谓的支持修改的主席树，其实我不太认为这是一个树套树，外面的那层树不够显然
int n,m,top,tot,sz; int v[10005],num[20005],A[10005],B[10005],K[10005],flag[10005],hash[20005],root[10005]; int sum[2200005],lch[2200005],rch[2200005]; int L[35],R[35],a,b;
这个题大概能看出来离线操作的一些端倪来
top是个游标来指示num数组的，num把题目中涉及到的值都存起来了，然后再用hash离散化处理
这里的离散化是因为主席树是一个完全二叉树，是对权值的建树，如果不把1,2,4,6,7变成1,2,3,4,5势必要浪费大量的空间
A,B,K和flag把所有的查询工作存起来了，这也是主席树的特性之一，如果是那种强制在线的题，只能常规树套树了
root是用来存每一个树状数组节点（C数组）所引出的主席树的根节点，sum，lch和rch应该是线段树家族的常客了
这里补充一下主席树的基本知识，首先对要进行操作的序列的前缀建权值树。每当询问[l, r]的时候，只要用[1, r]的树减去[1, l-1]的树,然后就可以查找第K小了 然后对每个前缀建树的时候，只需要新增Logn个点，连到前一个前缀所对应的线段树上，这样就仿佛建了n棵线段树一样 查询操作的话，我们只要找到对应这个区间的线段树，然后再去按照正常的主席树查询就可以了
其实查询操作就是正规的主席树查询而已，只不过我们把初始节点也执行了更新操作，这样原树为空，所有的东西就都依托于树状数组了
这里可以联想一下二维树状数组那里的，我可以维护原始数据的前缀和，只用树状数组维护delta，也可以索性全部update
如果是索性全部update的话，查询的时候就要先查树状数组找到若干树状数组节点，再查询这些节点对应的主席树了
int query(int l,int r,int k) { if(l==r) return l; int i,suml=0,sumr=0; for(i=1;i<=a;i++) suml+=sum[lch[L[i]]]; for(i=1;i<=b;i++) sumr+=sum[lch[R[i]]]; int mid=(l+r)>>1; if(sumr-suml>=k) { for(i=1;i<=a;i++) L[i]=lch[L[i]]; for(i=1;i<=b;i++) R[i]=lch[R[i]]; return query(l,mid,k); } else { for(i=1;i<=a;i++) L[i]=rch[L[i]]; for(i=1;i<=b;i++) R[i]=rch[R[i]]; return query(mid+1,r,k-(sumr-suml)); } }
最后查的结果是经过了离散化的，别忘了还原
更新操作就必须完全依赖树状数组了，更新都是先删再加，不管是删还是加，其根本的原理都是执行了一次insert，这样就会在原来的基础上多出logn个节点
这里我们就想到题目为啥要把所有的东西放在一起了，就是为了一块儿建树，更新的东西在查之前已经准备好了
再说说可持久化，可持久化是支持查询历史版本的，因为我的原始数据和更新数据都是一起建的，那么我更新之前和更新之后的东西，只要找到对应历史版本的树根查询就可以了
然后看一下更新操作：
void update(int last,int l,int r,int &rt,int w,int x) { rt=++sz; sum[rt]=sum[last]+x;lch[rt]=lch[last];rch[rt]=rch[last]; if(l==r) return; int mid=(l+r)>>1; if(w<=mid) update(lch[last],l,mid,lch[rt],w,x); else update(rch[last],mid+1,r,rch[rt],w,x); }
纯粹的主席树update,只不过需要调用logn次，毕竟有logn个树状数组点嘛
如果我们把历史版本的root覆盖了，当然就是真的覆盖了，就像本题一样，因为题目也没问历史版本怎么怎么样了
总的来说，主席树这个东西，值得去细细研究一番
而且通过这个题，离散化的板子有啦，哈哈
BZOJ1901：树套树之树状数组套主席树实现带修区间第K极值询问
原文：https://www.cnblogs.com/aininot260/p/9372788.html