首页 > 其他分享 >[学习笔记]主席树

[学习笔记]主席树

时间:2022-08-23 07:22:17浏览次数:108  
标签:int 线段 tree 笔记 学习 WR include 节点 主席

1. 静态主席树

主席树,即可持久化线段树,又称函数式线段树,是重要的可持久化数据结构之一。所谓可持久化,是指可以回溯到历史版本。

主席树的本质,就是在有数据更新时,在基准线段树的基础上采用“结点复用”的方式仅仅增加少量结点来维护历史数据,而不是通过存储不同版本线段树的方式来维护历史数据,从而达到减少时空消耗的目的

主席树空间一般建议是开 $n<<5$ ( $n$ 为基准线段树的结点数)。

如在下图中,橙色结点为历史结点,其右边多出来的结点是新结点(修改结点)。

 

 实现主席树时,需要经常用到前缀和、离散化等思想。

1. 前缀和:如需得到区间 $[L,R]$ 的统计信息,只需用区间 $[1,R]$ 的统计信息减去区间 $[1,L-1]$ 的统计信息就可以了。

2. 离散化:不改变数据相对大小的前提下,对数据进行相应的缩小。

利用前缀和,降低时间复杂度;利用离散化,降低空间复杂度。

 

洛谷例题:P3919 【模板】可持久化线段树 1(可持久化数组)

比较平凡地只支持单点修改和查询

 

#include<cstring>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000;
struct Chairman_Tree{
    int val;
    int lson,rson;
}tree[WR<<5];
int n,m;
int a[WR],root[WR];
int tot;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+ch-48;
        ch=getchar();
    }
    return s*w;
}
int add_point(int rt){
    tree[++tot]=tree[rt];
    return tot;
}
int build(int k,int l,int r){
    k=++tot;
    if(l==r){
        tree[k].val=a[l];
        return k;
    }
    int mid=(l+r)>>1;
    tree[k].lson=build(tree[k].lson,l,mid);
    tree[k].rson=build(tree[k].rson,mid+1,r);
    return k;
}
int modify(int k,int l,int r,int pos,int val){
    k=add_point(k);
    if(l==r){
        tree[k].val=val;
        return k;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) tree[k].lson=modify(tree[k].lson,l,mid,pos,val);
    else tree[k].rson=modify(tree[k].rson,mid+1,r,pos,val);
    return k;
}
int query(int k,int l,int r,int pos){
    if(l==r){
        return tree[k].val;
    }
    int mid=(l+r)>>1;
    if(pos<=mid) return query(tree[k].lson,l,mid,pos);
    else return query(tree[k].rson,mid+1,r,pos);
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    root[0]=build(root[0],1,n);
    for(int i=1;i<=m;i++){
        int rt=read(),opt=read();
        if(opt==1){
            int pos=read(),val=read();
            root[i]=modify(root[rt],1,n,pos,val);
        }
        else{
            int pos=read();
            printf("%lld\n",query(root[rt],1,n,pos));
            root[i]=root[rt];
        }
    }
    return 0;
}
View Code

 

求区间第K小:P3834 【模板】可持久化线段树 2

 

#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define WR WinterRain
using namespace std;
const int WR=1001000;
struct ChairMan{
    int lson,rson,val;//记录左儿子右儿子,还有一个大小
    ChairMan(){val=0;}//为了节约空间最好别用l,r
    //毕竟有丧心病狂的O(nlogn)空间……
}tree[WR<<4];//空间开大
int n,m,un;
int a[WR],b[WR];
int root[WR],tot;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-48;
        ch=getchar();
    }
    return s*w;
}
void pushup(int k){//这里相应的要改一下
    tree[k].val=tree[tree[k].lson].val+tree[tree[k].rson].val;
}
void cpy(int x,int y){
    tree[x].lson=tree[y].lson,tree[x].rson=tree[y].rson;
    tree[x].val=tree[y].val;
}
void build(int &k,int l,int r){//动态开点建树
    if(!k) k=++tot;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(tree[k].lson,l,mid);
    build(tree[k].rson,mid+1,r);
}
void insrt(int &k,int l,int r,int pos,int v){
    if(!k) k=++tot;
    cpy(k,pos);
    if(l==r){
        tree[k].val++;
        return;
    }
    int mid=(l+r)>>1;//权值线段树式的修改
    if(v<=mid) tree[k].lson=0,insrt(tree[k].lson,l,mid,tree[pos].lson,v);
    else tree[k].rson=0,insrt(tree[k].rson,mid+1,r,tree[pos].rson,v);
    pushup(k);
}
int query(int k,int l,int r,int pos,int v){
    if(l==r) return l;
    int tmp=tree[tree[k].lson].val-tree[tree[pos].lson].val;
    int mid=(l+r)>>1;
    if(v<=tmp) return query(tree[k].lson,l,mid,tree[pos].lson,v);
    else return query(tree[k].rson,mid+1,r,tree[pos].rson,v-tmp);
    //这里有一点点小差分,如果当前第k大在左子树里,直接查左子树
    //如果在右子树里,剪掉左子树大小再查询
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=b[i]=read();
    sort(b+1,b+1+n);
    un=unique(b+1,b+1+n)-b-1;//必备离散化
    build(root[0],1,un);//先建出权值线段树再说插入的事
    for(int i=1;i<=n;i++){
        a[i]=lower_bound(b+1,b+un+1,a[i])-b;
        //printf("a[i]=%d\n",a[i]);
        insrt(root[i],1,un,root[i-1],a[i]);
    }
    for(int i=1;i<=m;i++){
        int x=read(),y=read(),k=read();
        printf("%d\n",b[query(root[y],1,un,root[x-1],k)]);
    }
    return 0;
}
View Code

 

 2. 动态主席树

一. 基本原理

上面是简单的、在固定的数组上进行查询的主席树

如果在查询的同时支持对数组的点修改,不就更加NB了吗?

首先说明一下,动态主席树跟静态主席树在数据结构上已经有些差距了:

动态主席树说到底是线段树套线段树(外层可以简化为树状数组),而静态主席树是重复利用的线段树,两者是有一定区别的

但是,动态主席树用到了和静态主席树类似的实现思想,就是维护前缀和(元素出现次数的前缀和)

在上面的静态主席树中,我们使用了可持久化线段树来维护元素,而每个前缀和是一颗线段树:

虽然不同历史版本的线段树节点之间有交叉以重复利用,但每个历史版本都有唯一且独立的根节点

这就有点像我们求数列的区间和了:对于一个静态的数组 $a$,我们先计算前缀和 $pre_i=pre_{i−1}+a_i$,然后通过 $pre_R−pre_{L−1}$ 来求 $[L,R]$的区间和;

但是如果想求一个带修改的数组的区间和,必须使用高级数据结构,例如线段树/树状数组

在这里也是相似的,只不过区间中的元素从简单的数字变成了记录数值出现次数的线段树了

于是,我们可以考虑 外层是线段树/树状数组、内层是记录数值出现次数的区间和线段树 这样的结构

外层维护的是元素位置的区间:

如果我们想查询 $[L,R]$ 的第 $k$ 小,我们首先找的是外层的对应 $[1,R]$、$[1,L−1]$前缀和的几段区间(外层的节点,就是内层线段树的根节点)

外层的线段树的作用,是为了帮助我们找到位置区间对应的几颗内层线段树

内层维护的是数值的出现次数:

每棵线段树表示在根节点对应的外层区间中,每个数值出现的次数

二. 修改操作

如果将位置 $p_i$ 的数 $x$ 修改为 $y$,我们在外层线段树发现 $p_i$ 的位置一共被 $\log N$ 个区间(节点)包含;

同时,以每个节点为根节点的内层线段树中,分别各有 $\log N$ 个节点的值被 $x$、$y$ 影响

于是,对于外层每个包含 $p_i$ 的节点,我们都应该在以其为根节点的内层线段树中将数值 $x$ 的次数 $+1$ 、将数值 $y$ 的次数 $−1$,并一直更新到内层线段树的根节点

这样,一次修改的复杂度是 $\Theta(\log^2 N)$ 级别的

三. 查询操作

如果外层是线段树,对于每次区间 $[L,R]$ 的查询,我们都需要先在外层锁定仅包含区间 $[L,R]$ 的内层根节点,这组节点最多有 $\log N$ 个

然后我们就可以转化为静态主席树的简单版本了,只不过这棵线段树的每个节点的数值都是 以这组以节点为根的线段树 相同位置的节点 的数值之和(或者说,我们把这组线段树直接数值意义上的叠加在一起)

然后就是同上用类似二分的方法求区间第 $k$ 小,就不再赘述了

如果外层是树状数组,对于每次查询,我们都需要先在外层分别锁定仅包含区间 $[1,L−1]$、$[1,R]$ 的两组节点,每组节点最多有 $\log N$ 个

但是叠加成一颗线段树时,要减去 $[1,L−1]$ 这组的叠加,加上 $[1,R]$ 这组的叠加,后面还是一样的求区间第 $k$ 小

这样,一次查询的复杂度也是 $\Theta(\log^2N)$ 级别的

现在我们回到一开始的问题:如何解决爆炸的空间?

如果把内层线段树的节点全部事先开好的话,就的确是 $\Theta(N^2)$ 的了;但事实上,我们一共能访问到内层线段树的多少节点呢?

每次修改(基于原始数组初始化相当于修改 $N$ 次),同时间复杂度一样,是 $\log^2N$ 级别的

每次查询,仍然同时间复杂度一样,是 $\log^2 N$ 级别的,但是查询并不会对任何内、外层节点带来修改,所以没有必要开点】

这样一来,我们真正能访问到的,一共也就 $N\log^2N$ 个内层线段树的节点;剩下来的,想都不用想,全是 $0$,对于我们的查询并不会产生影响

所以,可以通过类似可持久化线段树的动态开点解决

#include<cstring>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
#define WR WinterRain
using namespace std;
const int WR=1001000;
struct Chairman_Tree{
    int val;
    int lson,rson;
}tree[WR*15];
struct Ask{
    int l,r,k,opt;
    int pos,t;
}ask[WR];
int n,m;
int root[WR];
int a[WR],modu[WR];
int tot,cnt;
int num[2],tmp[2][20];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+ch-48;
        ch=getchar();
    }
    return s*w;
}
int lowbit(int x){
    return x&(-x);
}
void modify(int &k,int l,int r,int pos,int val){
    if(!k) k=++tot;
    tree[k].val+=val;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(pos<=mid) modify(tree[k].lson,l,mid,pos,val);
    else modify(tree[k].rson,mid+1,r,pos,val);
}
void pre_modify(int pos,int val){
    int k=lower_bound(modu+1,modu+1+cnt,a[pos])-modu;
    for(int i=pos;i<=n;i+=lowbit(i)){
        modify(root[i],1,cnt,k,val);
    }
}
int query(int k,int l,int r){
    if(l==r) return l;
    int mid=(l+r)>>1,res=0;
    for(int i=1;i<=num[1];i++) res+=tree[tree[tmp[1][i]].lson].val;
    for(int i=1;i<=num[0];i++) res-=tree[tree[tmp[0][i]].lson].val;
    if(k<=res){
        for(int i=1;i<=num[0];i++) tmp[0][i]=tree[tmp[0][i]].lson;
        for(int i=1;i<=num[1];i++) tmp[1][i]=tree[tmp[1][i]].lson;
        return query(k,l,mid);
    }else{
        for(int i=1;i<=num[0];i++) tmp[0][i]=tree[tmp[0][i]].rson;
        for(int i=1;i<=num[1];i++) tmp[1][i]=tree[tmp[1][i]].rson;
        return query(k-res,mid+1,r);
    }
}
int pre_query(int k,int l,int r){
    // printf("%lld %lld %lld\n",k,l,r);
    memset(tmp,0,sizeof(tmp));
    num[0]=num[1]=0;
    for(int i=l-1;i;i-=lowbit(i)) tmp[0][++num[0]]=root[i]; 
    for(int i=r;i;i-=lowbit(i)) tmp[1][++num[1]]=root[i];
    return query(k,1,cnt);
}
signed main(){
    int t=read();
    while(t--){
        n=read(),m=read();
        memset(root,0,sizeof(root));
        memset(a,0,sizeof(a));
        cnt=0,tot=0;
        for(int i=1;i<WR*15;i++) tree[i].val=tree[i].lson=tree[i].rson=0;
        for(int i=1;i<=n;i++) a[i]=read(),modu[++cnt]=a[i];
        for(int i=1;i<=m;i++){
            char opt[10];
            scanf("%s",opt);
            if(opt[0]=='Q') ask[i].opt=1,ask[i].l=read(),ask[i].r=read(),ask[i].k=read();
            else ask[i].opt=0,ask[i].pos=read(),ask[i].t=read(),modu[++cnt]=ask[i].t;
        }
        sort(modu+1,modu+1+cnt);
        cnt=unique(modu+1,modu+1+cnt)-modu-1;
        for(int i=1;i<=n;i++) pre_modify(i,1);
        for(int i=1;i<=m;i++){
            if(ask[i].opt) printf("%lld\n",modu[pre_query(ask[i].k,ask[i].l,ask[i].r)]);
            else{
                pre_modify(ask[i].pos,-1);
                a[ask[i].pos]=ask[i].t;
                pre_modify(ask[i].pos,1);
            }
        }
    }
    return 0;
}
View Code

 

标签:int,线段,tree,笔记,学习,WR,include,节点,主席
From: https://www.cnblogs.com/WintersRain/p/16317149.html

相关文章

  • Dos命令学习day03
    打开CMD的方式开始——系统——命令提示符鼠标放在任意文件夹下面,按住Shift,单击右键,选择在此处打开命令行窗口(PowerShell)Wins键+R——搜索cmdWins键+E——在......
  • HCIA学习笔记十九:Hybrid端口的特殊通信方式
    一、Hybrid端口的特殊通信要求主机A和主机B都访问服务器C,但是它们直接不能互相访问。 interfaceGigabitEthernet0/0/1porthybridpvidvlan2porthybridunta......
  • 狂神说Java预科笔记
    狂神说Java预科笔记什么是计算机Computer:全称电子计算机,俗称电脑。能够按照程序进行,自动、高速处理海量数据的现代化智能电子设备。由硬件和软件组成常见形式......
  • Markdown学习
    Markdown学习标题#(几个#号代表几级标题)+空格  字体前后两个*:加粗前后一个*:斜体前后三个:*斜体加加粗前后两个~:划线 引用“>”学好数理化,走遍天下都......
  • Linux0.11源码学习(四)
    Linux0.11源码学习(四)linux0.11源码学习笔记参考资料:https://github.com/sunym1993/flash-linux0.11-talkhttps://github.com/Akagi201/linux-0.11http://xiehongfeng1......
  • HCIA学习笔记十八:Hybrid端口
    一、Hybrid端口简介•Hybrid端口是华三交换机上特有的端口类型,华为交换机出厂的时候,所有的接口默认都是Hybrid类型。• Hybrid端口即可以当Access端口来使用,也可以当Tr......
  • git推送分支学习
    转自:https://www.liaoxuefeng.com/wiki/896043488029600/900375748016320https://www.runoob.com/git/git-push.html1.push命令推送分支,就是把该分支上的所有本地提交(co......
  • vue3 学习-初识体验-常见指令v-for和v-model
    继续通过小案例来体验一些常用的指令,以经典的todolist进行展示.首先呢通过v-for指令进行dom循环.v-for通常是在循环dom的编写的同时遍历数据进行填充.<!DOCTYPEht......
  • 与 @上官苏 同学 的 学习对话
    这帖的起因是  上官苏 同学  @wwjjqq945   在  《【东风浩荡】东方学帝简介》   https://tieba.baidu.com/p/7984245232   33楼 发了......
  • python学习Day50
    Day50今日内容概要前端简介前端与后端前端的学习前端核心基础HTTP超文本传输协议四大特性数据格式响应状态码HTML简介简介HTML注释语法HTML文件结构......