title : 可持久化线段树

date : 2021-8-18
tags : 数据结构,ACM

可持久化线段树

可以用来解决线段树存储历史状态的问题。

我们在进行单点修改后，线段树只有logn个(一条链)的节点被修改，我们可以让修改后的树与修改前的树共享节点，节省时间和空间。

在学习之前，我们先引入三个前置知识：离散化、动态开点，权值线段树。

离散化

对于较大的数据范围，只要将关键点记录下来，记录下rank，就能把数据缩小到可以接受的范围，以便建立线段树或其他数据结构来解决问题。

具体步骤

（1）将所有端点加入辅助数组； （2）按坐标从小到大排序； （3）去重； （4）数据离散化，用hs数组记录端点的排名而非具体数字

vector<int>vt;
for(int i=1;i<=n;i++){
    cin>>a[i];
    vt.push(a[i]); //加入辅助容器
}
sort(vt.begin(),vt.end());//排序
vt.erase(unique(vt.begin(),vt.end()),vt.end()); //去重
for(int i=0；i<vt.size();i++){
    hs[vt[i]]=++tot; //存储为rank
}

动态开点

动态开点线段树可以避免离散化。

如果权值线段树的值域较大，离散化比较麻烦，可以用动态开点的技巧。

省略了建树的步骤，而是在具体操作中加入结点。

权值线段树

线段树的叶子节点保存的是当前值的个数。

每个节点保存区间左右端点以及所在区间节点的个数。

由于值域范围通常较大，一般会配合离散化或动态开点等策略优化空间。

应用

查找一个区间的第k大的值

查询某个数的排名

查询整个数组的排序

查询前驱和后继

单点修改

void update(int node,int start,int end,int pos){
    if(start==end) tr[node]++;
    else{
        int mid=start+end>>1;
        if(pos<=mid) update(node<<1,start,mid,pos);
        else update(node<<1|1,mid+1,end,pos);
    }
}//tr[i]表示值为i的元素个数,pos是要查找的位置

查询区间中的数出现次数

int query(int node,int start,int end,int ql,int qr){
    if(start==ql&&end==qr) return tr[node];
    int mid=start+end>>1;
    if(qr<=mid) return query(node<<1,start,mid,ql,qr);
    else if(ql>mid) return query(node<<1|1,mid+1,end,ql,qr);
    else return query(node<<1,start,mid,ql,qr)+query(node<<1|1,mid+1,end,ql,qr);
}//对单点查询同样适用

查询所有数的第k大值

int kth(int node,int start,int end,int k){
    if(start==end) return start;
    int mid=start+end>>1;
    int s1=tr[node<<1],s2=tree[node<<1|1];
    if(k<=s2) return kth(node<<2|1,mid+1,end,k);
    else return kth(node<<1,start,mid,k-s2);
} //注意是第k大，从右边开始减，如果是第k小就减去左边

查询前驱(后继同）

int findpre(int node,int start,int end){ //找这个区间目前最大的
    if(start==end) return start; //找到直接返回
    int mid=start+end>>1; 
    if(t[node<<1|1]) return findpre(node<<1|1,mid+1,end);
    return findpre(node<<1,start,mid);
}
​
int pre(int node,int l,int r,int pos){ //求pos的前驱
    if(r<pos){ //在最右边
        if(t[node]) return findpre(node,l,r);
        return 0;
    }
    int mid=l+r>>1,res;
    if(mid+1<pos&&t[node<<1|1]&& (res=pre(node<<1|1,mid+1,r,pos))) return res; //在右区间寻找
    return pre(node<<1,l,mid,pos);  //在左区间寻找
}

可持久化线段树

复杂度分析

建树O(nlogn)

询问为O(logn)

空间复杂度O(nlognlogn)。

核心思想

以前缀和形式建立，基于动态开点的存储形式。

两棵线段树之间是可减的（每一个节点对应相减）。

存储

hjt[0]充当NULL，从1开始储存根节点

struct Node{
    int lc,rc,sum; //左儿子右儿子和值sum
}hjt[maxn*32] //空间一般开到32即可
int cnt,root[maxn];//内存池计数器和根节点编号

插入

并不改变原来的树，而是新开根节点，并向下开辟

void insert(inr cur,int pre.int pos,int l,int r){
    if(l==r){ //找到这个点，当前版本点值+1
        t[cur].v=t[pre].v+1;
        return;
    }
    int mid=l+r>>1;
    if(pos<=mid){
        t[cur].lc=++e;
        t[cur].rc=t[pre].rc;
        insert(t[cur].lc,t[pre].lc,pos,l,mid);
    }else{
        t[cur].rc=++e;
        t[cur].lc=t[pre].lc;
        insert(t[cur].rc,t[pre].rc,pos,mid+1,r);
    }
    t[cur].v=t[t[cur].lc].v+t[t[cur].rc].v; //pushup
}

询问操作

本质上与权值线段树相同，只需要在区间上作差。

int query(int l,int r,int x,int y,int k){
    if (l == r){
        return l;   
    }
    int mid=(l+r)/2;
    int sum=tr[tr[y].l].sum-tr[tr[x].l].sum;
    if(sum >= k){ 
        return query(l,mid,tr[x].l,tr[y].l,k);
    }
    else{
        return query(mid+1,r,tr[x].r,tr[y].r,k-sum);
    }
}

区间第K小

luoguP3834 【模板】可持久化线段树 2（主席树）

#include <bits/stdc++.h>
​
using namespace std;
​
typedef long long ll;
const int maxn = 2e5 + 7;
​
int n, m, cnt, rt[maxn], a[maxn], x, y, k;
//a[i]是原始的序列，rt[i]是第i版本的主席树 
​
struct node
{
    int l, r, sum; //树的左端、右端和元素个数
} tr[maxn * 32];
​
vector<int> vt; //辅助容器
​
void read(int &data)  //快读优化
{
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            f = f * -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    data = x * f;
}
​
int getid(int x)  //返回每个元素的rank
{
    return lower_bound(vt.begin(), vt.end(), x) - vt.begin() + 1;
}
​
void insert(int l, int r, int &x, int y, int pos)
{ //每次修改或插入，新建一个根节点，并向下递归新建节点
    tr[++cnt] = tr[y]; 
    tr[cnt].sum++;  //区域元素数量+1
    x = cnt; //将原来的树地址指向当前树
    if (l == r)
    { //已经是叶子了，返回
        return;
    }
    int mid = (l + r) / 2;
    if (mid >= pos)
    {  //向左子树插入
        insert(l, mid, tr[x].l, tr[y].l, pos);
    }
    else
    {  //向右子树插入
        insert(mid + 1, r, tr[x].r, tr[y].r, pos);   
    }
}
​
int query(int l,