526互联

【学习笔记】可持久化线段树基础

发布时间 2023-10-17 07:29:32作者: Sonnety
点击查看目录

目录

前言

参考资料：oi-wiki

前置知识：

  • 线段树基本操作

  • 动态开点线段树

概念

可持久化线段树，又称主席树。

（事实上，据说，主席树应该是可持久化线段树的一个子集，主席树应该是单纯的针对静态查询第 \(k\) 小的问题，但是似乎大家都酱紫说主席树就是可持久化线段树）

引入一个问题：给定长度为 \(n\) 的序列 \(a\)，求其闭区间 \([x,y]\) 的第 \(k\) 小值。

似乎有许多做法，如分块+二分 \(O(n\sqrt{n}logn)\)，整体二分等。

但是如果用线段树来看这个问题呢？

如果我们对于每次插入一个数都建立一棵线段树，而线段树维护的权值 \(val\) 是当前值域 \([l,r]\) 中有多少个数，那么在 \(y\) 时的线段树节点 \(k\) 的 \(val\) 减去 \(x-1\) 时的线段树节点 \(k\) 的 \(val\) 就是 \([x,y]\) 区间内，值域在 \([l,r]\) 的数的数量。

所以我们查询第 \(k\) 小的点，如果 \(k\) 大于左子树的 \(val_2-val_1\)，那么这个点就在右子树，否则就在左子树。

大体思路已经成型，值域我们离散化就可以减小内存，但是问题在于我们如果真的每一个点都建一颗线段树，空间开销是巨大的，于是就有了可持久化线段树。

实现

现在我们增加了权值为 \(1\) 的点。

（图片来源：oi-wiki）

那么红色的点就被新增，这些红色的点所连成的树就恰好是我们修改后的树，而黑色节点所连成的树则是我们上一版本的树。

因此，我们称黑色节点练成的树叫历史版本。

单次修改可以新增 \(logn\) 个节点，如何增加节点？考虑从上往下动态开点。

在未遍历到子节点的时候，红色节点所连的边就指向自己历史版本的儿子，而当前的点进行动态开点。

// pre 指历史版本，id是动态开点的当前点，[l,r]是当前的值域，x是你要修改的点的值（离散后）
#define lid tr[id].lc
#define rid tr[id].rc
#define plid tr[pre].lc
#define prid tr[pre].rc
#define mid (l+r>>1)
void update(int pre,int &id,int l,int r,int x){
        id=++cnt;tr[id]=tr[pre];++tr[id].sum;// 每插入一个点其权值+1
        if(l==r)    return;
        (x<=mid)?update(plid,lid,l,mid,x):update(prid,rid,mid+1,r,x);
    }

于是，问题就解决了。

以【模板】可持久化线段树 2 为例，代码如下：

Miku's Code 
#include<bits/stdc++.h>
#define il inline
#define rg register int
#define cout std::cout
#define cerr std::cerr
#define push_back emplace_back
#define make_pair std::make_pair
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
typedef double ff;
typedef long double llf;
typedef std::pair<int,int> PII;
const ff eps=1e-8;
int Max(int x,int y){ return x<y?y:x; }
int Min(int x,int y){ return x<y?x:y; }
int Abs(int x){ return x>0?x:-x; }
// #if ONLINE_JUDGE
char INPUT[1<<20],*p1=INPUT,*p2=INPUT;
#define getchar() (p1==p2 && (p2=(p1=INPUT)+fread(INPUT,1,1<<20,stdin),p1==p2)?EOF:*p1++)
// #endif
il int read(){
    char c=getchar();
    int x=0,f=1;
    while(c<48) { if(c=='-')f=-1;c=getchar(); }
    while(c>47) x=(x<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}const int maxn=2e5+5;

int n,m,a[maxn],b[maxn],rt[maxn],cnt;

namespace PersistentSegementTree{
#define lid tr[id].lc
#define rid tr[id].rc
#define plid tr[pre].lc
#define prid tr[pre].rc
#define mid (l+r>>1)
    struct Tree{ int sum,lc,rc; };Tree tr[maxn<<5];
    void build_tree(int &id,int l,int r){
        id=++cnt;
        if(l==r)    return;
        build_tree(lid,l,mid);build_tree(rid,mid+1,r);
    }
    void update(int pre,int &id,int l,int r,int x){
        id=++cnt;tr[id]=tr[pre];++tr[id].sum;
        if(l==r)    return;
        (x<=mid)?update(plid,lid,l,mid,x):update(prid,rid,mid+1,r,x);
    }
    int query(int pre,int id,int l,int r,int x){
        if(l==r)    return b[l];
        int smid=tr[lid].sum-tr[plid].sum;
        return (x<=smid)?query(plid,lid,l,mid,x):query(prid,rid,mid+1,r,x-smid);
    }
#undef lid
#undef rid
#undef plid
#undef prid
#undef mid
}using namespace PersistentSegementTree;

il void input(){
    n=read(),m=read();
    for(rg i=1;i<=n;++i)  b[i]=a[i]=read(); 
    build_tree(rt[0],1,n);
    std::sort(b+1,b+1+n);
    for(rg i=1;i<=n;++i){
        int rank=std::lower_bound(b+1,b+1+n,a[i])-b;
        update(rt[i-1],rt[i],1,n,rank);
    }
}

int main(){
#ifndef ONLINE_JUDGE
freopen("tree.in","r",stdin);
freopen("tree.out","w",stdout);
#endif
    input();int l,r,k;
    while(m--){
        l=read(),r=read(),k=read();
        printf("%d\n",query(rt[l-1],rt[r],1,n,k));
    }
    return 0;
}

单次查询时间复杂度 \(O(logn)\)，总空间复杂度 \(O(nlogn)\)（近似）。

因此建议数组内存往大里开，建议开 maxn<<5。

例题：Tower Defense

题目链接

标记永久化

不会。