可持久化 & 树套树
0.前记
耗时很久，希望没锅锅少点
题单
-
- 可持久化数据结构
- 1.1 可持久化
- 1.2 可持久化线段树
- 1.3 静态区间第 k 小
- 1.4 可持久化 01Trie
-
- 树套树
- 2.1 树套树
- 2.2 二维树状数组
- 2.3 树状数组套平衡树
- 2.4 动态逆序对
- 2.5 三维偏序
1. 可持久化数据结构
可持久化线段树不是树，但我们可以看做每个时刻都有一棵树 。——lxl
1.1 可持久化
何为可持久化，我们可以看一下可持久化线段树的板题。我们发现，相比普通线段树，可持久化线段树引入了历史版本这一概念。换成人话，我们的每次操作都是基于之前的某一历史版本，每次操作后也会生成一个新版本，这就是可持久化。
要注意，每次操作不能影响到历史版本，所以我们操作时通常要新建结点，在新结点上操作。
1.2 可持久化线段树
可持久化线段树是最基础的可持久化数据结构，大部分思路在别的可持久化数据结构中也是大同小异的。那么怎么让线段树变得持久呢。
我们仍以板题为例。对于这道题，最朴素的想法便是每次将整个数组复制一遍，但显然这样做的话时\空间复杂度就会爆炸。我们考虑使用线段树。
如果每次我们都将整棵线段树复制一遍，显然这样是没有办法接受的。但是我们既然要用线段树这一优美的数据结构来实现，自然就要想到线段树的一优良性质，即：每次修改最多影响到 \(\log(n)\) 个结点。那我们每次复制时只复制被修改了的结点，其他没有被修改的结点直接利用原有结点，以此来降低复杂度。
如上图，如果我们需要更改 \([4,4]\) 这个结点的信息，我们仍是像普通线段树一样自顶向下更改，对于改变了的结点 \([1,4],[3,4],[4,4]\) ，我们复制出来一份，而别的结点我们利用原有结点即可。例如 \([1,4]\) 的左儿子直接指向历史版本的 \([1,2]\) 即可。
如同可持久化线段树，同为二叉结构的 Trie 树，（部分）平衡树也支持可持久化。
理解了思想，代码也就很好写了。
可持久化线段树中，区间修改只要像普通线段树一样区间修改，同样对修改路径上的点新建结点，再带个 lazytag 就可以保证复杂度正确；但由于我怕出锅并不常见，在此不多赘述，一般只会要求单点修改。
//空间需要开大
inline void build(int l,int r,int p)
{if(l==r){t[p].num=a[l];return ;}int mid=(l+r)>>1;build(l,mid,t[p].ls=++cnt);build(mid+1,r,t[p].rs=++cnt);push_up(p);return ;
}
inline void change(int l,int r,int p,int q,int x,int z)
{ //p为历史版本对应结点，q为当前版本新结点if(l==r){t[q].num=z;return ;}t[q].ls=t[p].ls,t[q].rs=t[p].rs;//先默认指向原左右儿子int mid=(l+r)>>1;//在左边就只新建左儿子，右边同理if(x<=mid) change(l,mid,t[p].ls,t[q].ls=++cnt,x,z);else change(mid+1,r,t[p].rs,t[q].rs=++cnt,x,z);push_up(q);return ;
}
inline int query(int l,int r,int p,int x)//单点查询
{if(l==r) return t[p].num;int mid=(l+r)>>1;if(x<=mid) return query(l,mid,t[p].ls,x);else return query(mid+1,r,t[p].rs,x);
}
inline int query(int l,int r,int p,int x,int y)//区间查询
{if(x<=l&&y>=r) return t[p].num;int mid=(l+r)>>1,ans=0;if(x<=mid) ans+=query(l,mid,t[p].ls,x,y);else ans+=query(mid+1,r,t[p].rs,x,y); return ans;
}
1.3 静态区间第 k 小
再来看一道典题。
区间 \([l,r]\)，考虑差分，我们很好用可持久化值域线段树维护。我们按顺序插入 \(a_i\)，每次插入就是一个版本，以上一个版本为历史版本，做单点修改。
对于第 \(i\) 棵值域线段树，维护每个结点代表的值域 \([x,y]\)中，有多少 \(x \leq a_j \leq y (j\leq i)\)。那么用第 \(r\) 棵线段树上的信息减去第 \(l-1\) 棵线段树，就是区间 \([l,r]\) 的信息。
比方说对于值域 \([x,y]\)，我们用第 \(r\) 棵线段树代表这个点的和减去第 \(l-1\) 棵线段树上的和，就代表在 \([l,r]\) 这个区间中有多少 \(x \leq a_i \leq y (l\leq i\leq r)\)。
到这里我们就可以二分答案，每次查询判断是否合法，设值域为 \(W\)，单次时间复杂度 \(O(\log^2 (W))\)。
但还可以优化，由于值域线段树结构是相同的，所以我们可以直接一起在线段树上二分，对于值域 \([x,y]\)，左儿子值域为 \([x,mid]\)，右儿子值域为 \([mid+1,y]\)；按照上述方法查询，如果 \([x,mid]\) 中有 \(\geq k\) 个数就进入左儿子，反之进入右儿子。 这样可以把外部二分的 \(\log\) 搞没，单次时间复杂度 \(O(\log (W))\)。
//还是结合代码理解吧
//定义同上面不同 l,r 代表值域范围；
//p,q 分别代表第 l-1,r 棵线段树上结点；
inline int query(int l,int r,int p,int q,int x)
{if(l==r) return l;int mid=(l+r)>>1;if(x<=t[t[q].ls].sum-t[t[p].ls].sum) return query(l,mid,t[p].ls,t[q].ls,x);else return query(mid+1,r,t[p].rs,t[q].rs,x-(t[t[q].ls].sum-t[t[p].ls].sum));
}
int main()
{while(m--){int l,r,k;cin>>l>>r>>k;cout<<query(-1e9,1e9,root[l-1],root[r],k)<<'\n';}
}
或者还可以把两维反过来，就是排序后扫描值域维，可持久化线段树维护序列，如果 \(a_i\geq x\) 就赋值为 1，反之赋值为 0。查询 \(x\) 对应的线段树上 \([l,r]\) 的和，就是在其区间中有多少数小于 \(x\)。然后仍二分答案，不再细说。
-
P3567 [POI2014]KUR-Couriers
-
P2839 [国家集训队]middle
1.4 可持久化 01Trie
可持久化字典树与可持久化线段树极度类似，可持久化字典树大多数是可持久化 01Trie，所以一般用在与位运算尤其是异或有关题目。
lxl 讲课时直接拿这当例题。所以直接说这道题。在树上、子树、路径、不带修改，所以没必要树剖——但不代表不可以树剖，而且树剖个人认为好理解，重点也不在这，所以我选了树剖。
不用树剖的话子树内转换成 DFS 序；路径上的话树上差分，维护每个点到根的可持久化 01Trie，每个点的 01Trie 在其父结点的 01Trie 上做修改得到,倍增求 LCA 转换成两条路径。所以维护两种可持久化 01Trie 就可以解决，后面是一样的道理。
剖完了以后我们按照 DFS 序建可持久化01Trie，将 \(a_i\) 变化成二进制形式，每次以 DFS 序前一版本为历史版本。二进制位是 0 就往左儿子递归，反之往右儿子。每经过一个结点就把这个结点的数 \(+1\)，代表在 \(1\) 到 \(i\) 中有多少数这一位为 \(0\setminus1\)。
inline void build(int x)
{//rel[x] 代表 dfs[rel[x]]=xint A=a[rel[x]],p=root[x]=++cnt,g=root[x-1];//以上一版本为历史版本for(register int i=30;i>=0;--i){if(A<(1<<i))//为0{//右儿子复制，左儿子新建，下面同理t[p].rs=t[g].rs,t[p].ls=++cnt;t[t[p].ls].num=t[t[g].ls].num+1;p=t[p].ls,g=t[g].ls;}else//为1{A-=(1<<i);//减掉这一位t[p].ls=t[g].ls,t[p].rs=++cnt;t[t[p].rs].num=t[t[g].rs].num+1;p=t[p].rs,g=t[g].rs;}}return ;
}
树剖后每次查询就是一个区间 \([x,y]\) 了，类比可持久化线段树，用第 \(r\) 棵 01Trie 与第 \(l-1\) 棵 01Trie 对应位上的数相减，若为真（大于 0）则说明在 \([x,y]\) 中存在一个数这一位为 \(0\setminus1\)。
然后求异或最大值肯定是贪心的使得高位异或得 1 即可，那么借鉴先前思路进行整体二分，二进制位从高到低，如果 \(z\) 这一位为 0，\([x,y]\) 中存在一个数这一位为 1，就直接进入右结点，并累加当前位答案，否则进入左结点。反之同理。
所以我们可以看出，与可持久化线段树的思路是差不多的。
inline int query(int x,int y,int z)
{//应该很好理解x=root[x-1],y=root[y];int ans=0;for(register int i=30;i>=0;--i){if(z<(1<<i)){if(t[t[y].rs].num-t[t[x].rs].num>0) ans+=(1<<i),x=t[x].rs,y=t[y].rs;else x=t[x].ls,y=t[y].ls;}else{z-=(1<<i);if(t[t[y].ls].num-t[t[x].ls].num>0) ans+=(1<<i),x=t[x].ls,y=t[y].ls;else x=t[x].rs,y=t[y].rs;}}return ans;
}
-
P3293 [SCOI2016]美味
-
P3302 [SDOI2013] 森林
2. 树套树
树套树和所谓的 cdq 分治功能差不多。——lxl
2.1 树套树
即一个数据结构“套着”另一个数据结构。
2.2 二维树状数组
二维树状数组即树状数组套树状数组，我们将原先树状数组上每一个点都改为一个树状数组，查询时类比原先一维查分，使用二维查分查询子矩阵内信息，这样我们就可以实现单点修改，矩阵求和了。
这题就是单点修改，但是要查询某个权值的矩阵和，值域很小，将第二维树状数组上每个点开一个桶就可以了。
inline int lowbit(int x){return x&(-x);}
inline void upd(int x,int y,int c,int A)
{while(x<=n){for(register int i=y;i<=m;i+=lowbit(i)) t[x][i][c]+=A;x+=lowbit(x);}return ;
}
inline int query(int x,int y,int c)
{int ans=0;while(x>0){for(register int i=y;i>0;i-=lowbit(i)) ans+=t[x][i][c];x-=lowbit(x);}return ans;
}
2.3 树状数组套平衡树
树状数组套平衡树可以通过大部分的树套树题。这道树套树板题要求我们实现单点修改和查询 k 在区间内的排名、区间内排名为 k 的值以及区间前驱\后继。
这个题面描述与平衡树类似，但普通平衡树的所有操作都是对于全局来的。对于这个题目可以抽象成单点修改，区间查询——类似树状数组。普通树状数组所支持的操作是：1.单点修改；2.区间 \([l,r]\) 和。那么我们将原先树状数组上的每个点都变成一颗平衡树，查询时在每棵平衡树上查询后将答案合并即可。
//对比一下普通树状数组的修改操作
inline void change(int x,int a)
{while(x<=n) t[x]+=a,x+=lowbit(x);return ;
}
但现在的每一个点都代表一个平衡树，所以我们要在每棵平衡树上修改。
inline void upd(int x,long long A,int k)
{while(x<=n){if(k==1) ins(x,A);//表示在平衡树上插入一个点if(k==-1) del(x,A);//删除一个点x+=lowbit(x);}return ;
}
查询同理，按照树状数组方法查询，合并答案即可。
//查询 k 在区间内的排名
//每次查询当前平衡树上有多少小于 k 的数，累加
inline int query(int pos,long long k)
{int ans=0;while(pos){split(root[pos],k-1,x,y);ans+=t[x].siz;root[pos]=merge(x,y);pos-=lowbit(pos);}return ans;
}
//查询区间内排名为 k 的值
//二分值域维，查询得到有多少数小于 mid
inline long long query_2(int l,int r,int k)
{long long cl=MIN,cr=MAX;while(cl<cr){long long mid=(cl+cr+1)>>1;(query(r,mid)-query(l-1,mid)+1<=k)?cl=mid:cr=mid-1;}return cl;
}
2.4 动态逆序对
动态逆序对可以用树套树或 cdq 分治解决。
在一个序列中，第 \(i\) 个数 \(a_i\) 对逆序对个数的贡献是在 \([1,i-1]\) 中大于 \(a_i\) 的数的个数（即 \([1,i-1]\)中数的总个数减去小于等于 \(a_i\) 的数的个数）加上在 \([i+1,n]\) 中小于 \(a_i\) （即 \([1,n]\)中小于 \(a_i\) 的数的个数减去 \([1,i]\) 小于 \(a_i\) 的数的个数） 的数的个数，最后转化成查询区间内小于 \(x\) 的数，容易使用树状数组套平衡树维护。
for(register int i=1;i<=n;++i) ANS+=i-1-query(i-1,a[i]+1);//先求出所有
while(m--)
{cout<<ANS<<'\n';int i;cin>>i;i=p[i];//找到 a[i]=x 的位置ANS-=(query(i-1,INF)-query(i-1,a[i]+1))+(query(n,a[i])-query(i,a[i]));/*这里找前面有多少大于 a[i] 时，前面的数可能有被删掉的所以不能直接用 i-1 减 query(i-1,a[i]+1)，要查询 query(i-1,INF)*/upd(i,a[i],-1);
}
- P3759 [TJOI2017]不勤劳的图书管理员
2.5 三维偏序
既然树套树和 cdq 分治功能差不多，那么 cdq 分治的版题三维偏序也是可以用树套树实现。
类比 cdq 分治，分别以第一维、第二维、第三维为第一、第二、第三关键字排序，这样 \(a_i\leq a_j\) 转换成了 \(i\leq j\)，按照排序后顺序操作就可以解决第一维；问题转化成了找到 \(b_i\leq b_j,c_i\leq c_j\)，即区间 \([1,b_j]\) 中小于等于 \(c_i\) 的数的个数，用树状数组套平衡树维护。
发现如果一组数与另一组数三维完全相同时，排在前面的会漏算，开个桶记录每种有多少个，把漏算的加上即可（\(SUM = a_i\times10^{10} + b_i\times10^5 + c_i\)）。
inline void upd(int x,int a)
{while(x<=K) ins(x,a),x+=lowbit(x);return ;
}
inline int query(int x,int k)
{int ans=0;while(x){split(root[x],k,X,Y),ans+=t[X].siz;//是小于等于 k 捏root[x]=merge(X,Y);x-=lowbit(x);}return ans;
}
for(register int i=1;i<=n;++i)
{cin>>a[i].a>>a[i].b>>a[i].c;T[SUM]++;
}
sort(a+1,a+n+1,cmp);
for(register int i=1;i<=n;++i)
{int now=query(a[i].b,a[i].c)+T[SUM]-1;// -1 把自身排除ans[now]++,T[SUM]--;upd(a[i].b,a[i].c);
}
