可持久化线段树（主席树）学习笔记

迷南。 2021-12-21 04:11 298阅读 0赞

# 主席树 #

一种神奇数据结构，更令人半懂不懂的说法是叫做可持久化权值线段树

## 名字由来 ##

据说发明者叫做HJT，于是就有人联想到了某国家领导人

于是就有人称其为主席树了

## 主席树可以解决什么问题？ ##

最著名的应当算是静态区间K小了吧

后面会讲到的

## 主席树的实现 ##

主席树易于理解，代码又短，超喜欢这个数据结构的

嗯，先拿一道题当例子来说一说，然后再讲讲静态区间K小怎么写吧

### 洛谷P3919 【模板】可持久化数组（可持久化线段树/平衡树） ###

首先看到题面，大家的想法：肯定线段树啊。

但是如果用线段树的话，怎么做到历史版本查询呢？

最简单的想法，直接复制整棵树。

然而这样不仅空间爆炸时间还爆炸

于是我们就改用一种神奇的方法节省空间和时间

即，在每创建一个新版本的时候，只复制那条被更改了的链，而其他的按照原样不动

这样就是可持久化线段树了

放图：

![Vq1kMn.png][]

那我们怎样才能做到新建这么一条链呢？

我们在更改的时候，遍历到了哪个节点，我们就新建这个节点呗

应题目要求，查询的时候我们也要新建一个版本，那我们直接建一个新的根就好了

详细的就看代码实现吧

完整代码：

#include<bits/stdc++.h>
    using namespace std;
    struct node{//正常线段树声明
        int l,r;
        int sum;
    }tree[20000001];
    int rt[20000001];//根的编号，因为我们每一个版本就会有一个新的根，所以我们rt[i]即代表第i个版本的根节点
    int cnt;
    int a[20000001];
    void build(int &t,int l,int r){//建树，因为一开始是没有变化的，所以我们建树是和普通线段树一模一样的
        t=++cnt;
        if(l==r){
            tree[t].sum=a[l];
            return;
        }
        int mid=(l+r)/2;
        build(tree[t].l,l,mid);
        build(tree[t].r,mid+1,r);
    }
    int update(int o,int l,int r,int x,int y){//重点：更改
        int q=++cnt;//建立这个新的节点
        tree[q].l=tree[o].l;//把原本节点的信息拷贝过来
        tree[q].r=tree[o].r;
        tree[q].sum=0;//初始化为0
        //cout<<q<<" "<<l<<" "<<r<<endl;
        if(l==r){//如果已经是叶子节点了我们就赋值然后跑路
            tree[q].sum=y;
            return q;//把新节点的编号返回到上一级
        }
        int mid=(l+r)/2;
        if(x<=mid)tree[q].l=update(tree[q].l,l,mid,x,y);//这里和原来的线段树很相似，不过我们一样是要更新节点的
        //我们这么做也是一样的，要把自己的儿子指针指向修改过的哪个，而不是上一个版本的那个
        else tree[q].r=update(tree[q].r,mid+1,r,x,y);
        return q;//最后把这个新节点的编号返回到上一级，然后让上一层的新节点的儿子指向自己
    }
    int query(int o,int l,int r,int x){//查询，一模一样的
        int ans;
        if(l==r)return tree[o].sum;
        int mid=(l+r)/2;
        if(x<=mid)ans=query(tree[o].l,l,mid,x);
        else ans=query(tree[o].r,mid+1,r,x);
        return ans;
    }
    int main(){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)scanf("%d",&a[i]);
        build(rt[0],1,n);//首先建立一棵正常的线段树
        for(int i=1;i<=m;i++){
            int root,opt,x;
            scanf("%d%d%d",&root,&opt,&x);
            if(opt==1){
                int y;
                scanf("%d",&y);
                rt[i]=update(rt[root],1,n,x,y);//新的根也要更新一下，记录一下当前版本的根的编号
            }
            else{
                printf("%d\n",query(rt[root],1,n,x));//按题目说的查询版本root的信息
                rt[i]=rt[root];//没有任何改变所以第i个版本的根直接指向这个root就好了
            }
        }
    }

好了，可持久化线段树的基本实现就完成了，现在我们就来看一看主席树咯

### 洛谷P3834 【模板】可持久化线段树 1（主席树） ###

静态区间K小？估计大家一眼看下去就会想什么排序之类的暴力吧

但我们今天就不，我们要用线段树解决

我们先看一个简化了的问题：如何解决整体K小？

这时候就要用到我们的权值线段树了

#### 权值线段树 ####

我们现在维护的不是原本的每一个数的值，而是每个数在什么范围了

首先离散化（否则很难维护），接下来的可以看看图：

![Vqa1QU.png][]

那怎么找到第K小是哪一个呢？

因为这个权值线段树是按数字的数量来维护的，所以我们可以把：`1~4区间中共有4个数`理解为`排名为4或比4小的一定在1~4区间中`以及`排名比4大的一定在它的兄弟中`

那么我们就可以按照这样的思维往下找，直到叶子节点，那么这个叶子节点所代表的数就是第K大的了

代码实现：

#include<bits/stdc++.h>
    using namespace std;
    struct qwq{
        int l,r;
        int sum;
    }tree[2000001];
    int num[2000001];
    int ton[2000001];
    map<int,int> mp;
    int cnt;
    void build(int o,int l,int r){
        if(l==r){
            tree[o].sum=ton[l];
            return;
        }
        int mid=(l+r)/2;
        build(o*2,l,mid);
        build(o*2+1,mid+1,r);
        tree[o].sum=tree[o*2].sum+tree[o*2+1].sum;
    }
    int get(int k,int o,int l,int r){
        if(l==r){
            return l;
        }
        int mid=(l+r)/2;
        if(k>tree[o*2].sum){
            return get(k-tree[o*2].sum,o*2+1,mid+1,r);
        }
        else {
            return get(k,o*2,l,mid);
        }
    }
    int rea[2000001];
    int main(){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;++i){
            scanf("%d",&num[i]);
            if(!mp[num[i]]){
                rea[++cnt]=num[i];
                num[i]=mp[num[i]]=cnt;
            }
            else num[i]=mp[num[i]];
        }
        for(int i=1;i<=n;++i){
            ton[num[i]]++;
        }
        build(1,1,n);
        int m;
        scanf("%d",&m);
        for(int i=1;i<=m;++i){
            int k;
            scanf("%d",&k);
            printf("%d\n",rea[get(k,1,1,n)]);
        }
    }

#### 主席树 ####

可能有人看完上面的整体K小，会想：什么鬼玩意儿，直接排序不就好了吗。

那么接下来，我会告诉你这个整体K小有什么用。

首先，在主席树中，对于一个以i为根的节点\{l,r\}来说，它代表的是前i项中，在区间l~r中的数字出现个数（当然是离散化过后的）。

那我们要知道某区间l1,r1中在区间l~r中的数字出现个数怎么算呢？我们就用1~r1中在区间l~r的数字个数减去l~l1-1中在区间l~r的数字个数就可以了

之后的查询与上面的权值线段树是类似的

具体的细节可以看一看代码实现啦

#include<bits/stdc++.h>
    using namespace std;
    struct node{
        int l,r;
        int sum;
    }tree[5000001];
    int rt[200001];
    int a[200001];
    int b[200001];
    int cnt;
    int p;
    void build(int &t,int l,int r){//正常的建树
        t=++cnt;
        if(l==r)return;
        int mid=(l+r)/2;
        build(tree[t].l,l,mid);
        build(tree[t].r,mid+1,r);
    }
    int update(int o,int l,int r){//更新
        int q=++cnt;//和之前的可持久化线段树一样，要新建一条链
        tree[q]=tree[o];
        tree[q].sum++;//代表这个区间中的数出现次数+1
        if(l==r){
            return q;
        }
        int mid=(l+r)/2;
        if(p<=mid)tree[q].l=update(tree[q].l,l,mid);
        else tree[q].r=update(tree[q].r,mid+1,r);
        return q;
    }
    int query(int u,int v,int l,int r,int k){
        int ans;
        if(l==r)return l;
        int mid=(l+r)/2,x=tree[tree[v].l].sum-tree[tree[u].l].sum;//按照之前的，求出来l~r区间中数字范围在l~r中的出现次数
        if(x>=k)ans=query(tree[u].l,tree[v].l,l,mid,k);//接下来的就差不多了
        else ans=query(tree[u].r,tree[v].r,mid+1,r,k-x);
        return ans;
    }
    int main(){
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i){
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        sort(b+1,b+n+1);
        int que=unique(b+1,b+1+n)-b-1;//离散化后的数组的长度
        build(rt[0],1,que);//建树
        for(int i=1;i<=n;++i){
            p=lower_bound(b+1,b+que+1,a[i])-b;//查询a[i]这个值在b数组里代表的是多少
            rt[i]=update(rt[i-1],1,que);//然后新建节点，代表1~i这个区间里在原来的基础上（即1~i-1）添加一次a[i]在b中的值的出现次数
        }
        for(int i=1;i<=m;++i){
            int l,r,k;
            scanf("%d%d%d",&l,&r,&k);
            printf("%d\n",b[query(rt[l-1],rt[r],1,que,k)]);//查询
        }
    }

然后这道板子题就完美的解决了。

## 总结 ##

其实这个主席树的可持久化就体现在每次新增一条链里面了

反正是个很神奇的数据结构

以后如果有时间的话也会写一下动态主席树的

转载于:https://www.cnblogs.com/youddjxd/p/11041441.html

[Vq1kMn.png]: /images/20211221/427269fa0d184ceaa6827d51d59a02c5.png
[Vqa1QU.png]: /images/20211221/75e41d62db904b5aa89dcb9765482fca.png