这节课学的不咋会，而且感觉不咋通用，就随便写写看吧
适用的是数发生变化和求区间的某种属性等等
可持久化的前提：本身的拓扑排序结构不变
可持久化的操作相当于git仓库的存储方式，可以查找和存储所有的历史版本，核心思想只记录每一个版本与上一个版本不同的节点 ，然后用一棵树的结构来连接不同的地方，相同的地方直接copy过来就行
1.tire树的可持久化
（1）普通的tire ——》版本一
（2） 版本一 ——》版本二
（3）版本二 ——》版本三
（4）版本三 ——》版本四
最大异或和
#include<bits/stdc++.h> using namespace std; const int N=600010,M=N*25; int n,m; int s[N];//存异或前缀和 int tr[M][2],max_id[M];//tr存tire树版本,max_id存的是某个节点最大的id int root[N],idx;//记录根节点序列 void insert(int i,int k,int p,int q)//当前第几位 当前处理到第几位 上一个版本 当前最新版本 { if(k<0) { max_id[q]=i;//处理到最后一位，则max_id=i return; } int v=s[i]>>k&1;//获取当前位 if(p) tr[q][v^1]=tr[p][v^1];//假如上一个节点存在，直接复制过来 tr[q][v]=++idx;//给当前位开一个新的点 insert(i,k-1,tr[p][v],tr[q][v]);//插入下一位 max_id[q]=max(max_id[tr[q][0]],max_id[tr[q][1]]);//左右子节点取最大 } int query(int root,int C,int L)//当前节点 C就是s[n]^x L就是左边限制 { int p=root; for(int i=23;i>=0;i--) { int v=C>>i&1;//获取当前位 if(max_id[tr[p][v^1]]>=L) p=tr[p][v^1];//假如这个节点的当前位的对立面有的化 else p=tr[p][v];//反之只能将就了 } return C^s[max_id[p]];//返回答案 } int main() { scanf("%d%d",&n,&m); max_id[0]=-1;//0初始化为最小的数就行了 root[0]=++idx;//第0个版本分配一个idx insert(0,23,0,root[0]);//处理第0个版本 for(int i=1;i<=n;i++) { int x; scanf("%d",&x); s[i]=s[i-1]^x;//前缀和异或 root[i]=++idx;//开辟新的节点 insert(i,23,root[i-1],root[i]);//插入这个版本 } char op[2]; int l,r,x; while(m--) { scanf("%s",op); if(*op=='A') { scanf("%d",&x); n++; s[n]=s[n-1]^x;//前缀异或和 root[n]=++idx;//开辟新的节点 insert(n,23,root[n-1],root[n]);//更新新的版本 } else { scanf("%d%d%d",&l,&r,&x); printf("%d\n",query(root[r-1],s[n]^x,l-1));//输出r-1版本中数大于l-1的数 } } return 0; }
2.线段树的可持久化——主席树
第K小数
先求1~R的版本中[l,r]的个数cnt1，在求1~L的版本中[l,r]的个数cnt2,cnt=cnt1-cnt2则为下标区间[L,R]在这个数值[l,r]的增加的个数，然后二分求第k小数，k<=cnt递归左边反之递归右边
#include<bits/stdc++.h> using namespace std; const int N=100010,M=10010; int n,m; int a[N]; vector<int> nums; struct Node { int l,r;//这里的l,r不是区间是左右子树的下标 int cnt;//记录当前树的这个区间有多少个数 }tr[N*4+N*17]; int root[N],idx;//记录不同的版本 int find(int x)//离散化的二分查找 { return lower_bound(nums.begin(),nums.end(),x)-nums.begin(); } int built(int l,int r)//建立线段树 { int p=++idx;//分配一个节点 if(l==r) return p; int mid=l+r>>1; tr[p].l=built(l,mid),tr[p].r=built(mid+1,r);//左右建立线段树 return p; } int insert(int p,int l,int r,int x) { int q=++idx;//开辟一个新的节点，也即新的版本 tr[q]=tr[p];//先把上一个版本复制过来 if(l==r)//假如是叶节点 { tr[q].cnt++; return q; } int mid=l+r>>1; if(x<=mid) tr[q].l=insert(tr[p].l,l,mid,x);//假如在左边，则插入在左边 else tr[q].r=insert(tr[p].r,mid+1,r,x);//假如在右边，则插入在右边 tr[q].cnt=tr[tr[q].l].cnt+tr[tr[q].r].cnt;//更新一下cnt return q; } int query(int q,int p,int l,int r,int k) { if(l==r) return l;//假如是叶节点，则答案就是叶节点 int cnt=tr[tr[q].l].cnt-tr[tr[p].l].cnt;//算一下左边区间增加的cnt个数 int mid=l+r>>1; if(k<=cnt) return query(tr[q].l,tr[p].l,l,mid,k);//假如左边的数大于等于k，则第k小数在左边 else return query(tr[q].r,tr[p].r,mid+1,r,k-cnt);//反之在右边，右边则找第k-cnt小数，因为左边已经有cnt个小数了 } int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); nums.push_back(a[i]);//进行离散化 } //去重 sort(nums.begin(),nums.end()); nums.erase(unique(nums.begin(),nums.end()),nums.end()); root[0]=built(0,nums.size()-1);//初始化第0个版本，也即创立线段树 for(int i=1;i<=n;i++) root[i]=insert(root[i-1],0,nums.size()-1,find(a[i]));//把每个值插进当前版本里 while(m--) { int l,r,k; scanf("%d%d%d",&l,&r,&k); printf("%d\n",nums[query(root[r],root[l-1],0,nums.size()-1,k)]);//询问整个区间的l-1~r版本的增加的数中的第k小数 } return 0; }
