可持久化数据结构——最大异或和(trie)+第K小数(线段树)

可持久化数据结构：可以存下数据结构的所有历史版本：

核心思想：只记录和前一个版本不一样的节点。

可持久化trie数构造过程：

与Trie的节点一样，可持久化trie的每一个节点也有若干字符指针指向子节点，可以用trie[x,c]保存节点x的字符指针C指向的子节点的编号。插入新的字符串操作如下、

1.设p等于当前trie的根节点root,i=0;

2.建立一个新的节点q=++idx

3.检查p是否为空，为空的话则不用对q做额外操作，不为空的话应该先将p上的所有信息先复制到q节点下面，也就是让q指向p的所有子节点。也就是对于每一种字符C，令trie[q,c]=trie[p,c].

4.为新的要插入字符si建立一个新编号q`=++idx,令trie[q,si]=q`。

5.令p=trie[p,si],(这里p下次会用于上面的检查是否为空),q=trie[q,si], i=i+1(指向下一个要插入的字符).

6.然后重复步骤3~5.

图示：略

传送门：256. 最大异或和 - AcWing题库
思路：

本题需要将数字转化成二进制01串进行插入，

针对题目中的查询操作，建立一个新的前缀和数组S[i]表示前i个数字异或的和=A1^A2^...Ai.

对于询问操作里面Ap^...AN^ x 转换成到前缀和数组就是Sp-1^SN^ x,询问就是变成了在l~r之间选择一个p使得Sp-1^SN^ x最大，其中SN^ x是定值。

可持久化的trie可以查询历史版本的trie，

对于区间[l,r]只要查询root[r]的字典树就可以得到1~r(解决r)里面可以使得Sp-1^SN^ x最大的p值。

对于左边界l，可以在trie树的每一个节点上面记录一个max_id为当前子树中下标最大的值，如果标记大于l则可以进入左子树进行查找(解决l)。
代码：

#include
#include
#include
using namespace std;
typedef long long ll;
const int N=6e5+10,M=N*25;
int n,m;
int s[N];
int tr[M][2];
int max_id[M],idx;
int root[N];
void insert(int i,int k,int p,int q)
{
    if(k<0)
    {
        max_id[q]=i;  //当前这个数字的编号。
        return;
    }
    int v=s[i]>>k&1;
    if(p) tr[q][!v]=tr[p][!v];//把上一版本的p的其余节点都复制到q节点下来
    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]]); //pushup操作
}
int query(int root,int c,int l)  //查询root版本下面与C异或和最大的一个前缀和s[p-1],其中限制为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;
    root[0]=++idx;
    insert(0,23,0,root[0]); //因为后面要用到s[0]的值，所以s[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));
        }
    }
 
        return 0;
}

线段树的可持久化操作：

首先，线段树的可持久化的结构其实跟trie的结构是差不多的。

然后可持久化线段树里面存的l,r不再是下标，而是数值区间。

传送门：255. 第K小数 - AcWing题库

思路：原题的数值范围很大，但是区间范围却很小，所以这里需要对数据做离散化。

和可持久化trie树一样用一个root[i]表示第i个版本的线段树，线段树里面会存一个cnt表示前p个元素里面在tr[p].l到tr[p].r之间的元素的数量有多少个，要求[l,r]的原区间里面第k小的元素要用第r个版本的线段树的cnt减去第l-1个版本的cnt，这个结果才是数组区间[l,r]里面的元素统计的数量。

未完待续....

代码：

#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N=1e5+10,M=1e4+10;
int n,m;
int a[N];
vector<int>nums;
struct node
{
    int l,r;
    int cnt; //表示在l,r之间的元素的个数
}tr[N*4+N*17];
int idx,root[N];
int find(int x) //获取离散化之后的元素下标？
{
    return lower_bound(nums.begin(),nums.end(),x)-nums.begin();
}
int build(int l,int r)
{
    int p=++idx;
    if(l==r) return p;
    int mid=l+r>>1;
    tr[p].l=build(l,mid);
    tr[p].r=build(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;
 
    return q;
}
int query(int q,int p,int l,int r,int k) //
{
    if(l==r) return r;
    int cnt=tr[tr[q].l].cnt-tr[tr[p].l].cnt;
    int mid=l+r>>1;
    if(k<=cnt)return query(tr[q].l,tr[p].l,l,mid,k);
    else return query(tr[q].r,tr[p].r,mid+1,r,k-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]=build(0,nums.size()-1);
 
    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)]);
    }
        return 0;
}