主席树（可持久化线段树）与标记永久化：原理与应用详解

主席树（可持久化线段树）与标记永久化：原理与应用详解

引用

CSDN

1.

https://blog.csdn.net/2301_79199219/article/details/139031325

主席树，又称可持久化线段树，是一种在算法竞赛中常用的高级数据结构。它通过维护多个版本的线段树，支持高效的历史版本查询和修改操作。本文将从点查点修区间历史、静态区间第k小以及标记永久化三个方面，深入讲解主席树的原理和应用。

点查点修区间历史

主席树的核心思想是维护时间轴和序列轴。通过将每次修改操作都视为一个新的版本，主席树能够支持对任意历史版本的查询。

问题背景

考虑一个经典问题：给定一个数组，支持两种操作：

1. 单点修改：将数组中某个位置的值修改为新值
2. 单点查询：查询数组中某个位置的值

要求支持对任意历史版本的查询。

解决方案

最暴力的解决方案是每次操作都复制整个数组，但这种方法显然会超出内存限制。优化的关键在于复用。

一种直观的优化思路是，直接复用之前的数组，但将修改的内容记录下来。然而，当修改内容过多时，每次查询的时间开销会变得很大。

进一步优化的方法是使用线段树。线段树的每个节点只维护其子树范围内的信息，这样可以很容易地复用那些没有被修改过的节点。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
struct node {
    int ls,rs,val;
    int id;
}tree[N<<5];
int cnt;
int head[N];
int a[N];
void build(int &p, int l, int r){
    p = ++cnt;
    if(l == r){
        tree[p].val = a[l];
        return;
    }
    int mid =  (l+r)>>1;
    build(tree[p].ls, l, mid);
    build(tree[p].rs, mid+1, r);
}
void update(int &p, int pre, int l, int r, int index, int val){
    p = ++cnt;
    tree[p] = tree[pre];
    if(l == r){
        tree[p].val = val;
        return;
    }
    int mid = (l+r)>>1;
    if(index <= mid) update(tree[p].ls, tree[pre].ls, l, mid, index, val);
    else update(tree[p].rs, tree[pre].rs, mid+1, r, index, val);
}
int query(int p, int l, int r, int index){
    if(l == r) return tree[p].val;
    int mid = (l + r) >> 1;
    if(index <= mid) return query(tree[p].ls, l, mid, index);
    else return query(tree[p].rs, mid + 1, r, index);
}
int main(){
    ios::sync_with_stdio (0);
    cin.tie (0);
    cout.tie (0);
    int n,m;
    cin>>n>>m;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    build(head[0], 1, n);
    int cur = 1;
    for(int i = 1; i <= m; i++){
        int op, pre;
        cin>>pre>>op;
        if(op == 1){
            int index, val;
            cin>>index>>val;
            update(head[i], head[pre], 1, n, index, val);
        }else{
            int index;
            cin>>index;
            cout<<query(head[pre], 1, n, index)<<endl;
            head[i] = head[pre];
        }
    }
    return 0;
}

代码解析

为什么需要写build函数？如果使用动态开点权值线段树，可以不需要build函数，使用如下代码：

void insert(ll& p,ll l,ll r,ll x,ll k){
    if(!p) p = ++cnt;
    if(l == r){
        tree[p].sum += k;
        return;
    }
    ll mid = (l + r)/2;
    if(x <= mid) insert(tree[p].l,l,mid,x,k);
    else insert(tree[p].r,mid+1,r,x,k);
    tree[p].sum += k;
}

注意，这与主席树的代码有什么不同？不同之处在于这一句：

if(!p) p = ++cnt;

在主席树中，我们没有判断!p。这是因为主席树每次都要依赖上一个树来构建，我们需要复制pre节点的内容，并更新经过的节点ID。参考下图，粉色部分表示新开出来的链。

而动态开点是，开出没有的点，已经经过的点就没必要再开了。主席树的update函数需要接受pre节点，必须先有一个原树才能进行更新。如果不另外写一个change函数，就无法避免使用build函数。

总结来说，主席树的update依赖于pre树，需要开出一条新链，因此不能直接在这里初始化。

静态区间第k小

主席树还可以用于解决静态区间第k小的问题。在这种场景下，主席树维护序列轴和值域轴。

代码实现

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 2e5 + 5;
const int M = 1e9 + 5;
struct node {
    int ls,rs,sum,id;
}tree[N<<6];
int cnt;
void update(int &p, int pre, int l, int r, int x){
    p = ++cnt;
    tree[p] = tree[pre];
    tree[p].sum = tree[pre].sum + 1; //标记永久化的写法
    if(l == r){
        // tree[p].sum = tree[pre].sum + 1;  //pushup的写法
        return;
    }
    int mid = (l+r)>>1;
    if(x <= mid) update(tree[p].ls, tree[pre].ls, l, mid, x);
    else update(tree[p].rs, tree[pre].rs, mid+1, r, x);
    // tree[p].sum = tree[tree[p].ls].sum + tree[tree[p].rs].sum;  //pushup的写法
}
int query(int L, int R, int l, int r, int k){ //二分找到最大节点
    if(l == r) return l;
    int mid = (l+r)>>1;
    int left_sum = tree[tree[R].ls].sum - tree[tree[L].ls].sum;
    if(k <= left_sum) return query(tree[L].ls, tree[R].ls, l, mid, k);
    else return query(tree[L].rs, tree[R].rs, mid+1, r, k-left_sum);
}
int head[N];
int main(){
    ios::sync_with_stdio (0);
    cin.tie(0), cout.tie(0);
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        int x;
        cin>>x;
        update(head[i], head[i-1], 0, M, x);
    }
    for(int i = 1; i <= m; i++){
        int L,R,k;
        cin >> L >> R >> k;
        cout<<query(head[L-1], head[R], 0, M, k)<<endl;
    }
    return 0;
}

标记永久化

在处理线段树时，我们通常需要pushup和pushdown操作。但在主席树中，由于节点的共用特性，我们可以采用标记永久化的策略，避免复杂的上下推操作。

代码实现

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;
const ll N = 1e5 + 5;
ll a[N], head[N];
struct node{
    ll l,r,sum,add;
}tree[N<<6];
ll cnt;
void build(ll& p, ll l, ll r){
    p = ++cnt;
    if(l == r){
        tree[p].sum = a[l];
        return;
    }
    ll mid = (l+r)>>1;
    build(tree[p].l, l, mid);
    build(tree[p].r, mid+1, r);
    tree[p].sum = tree[tree[p].l].sum + tree[tree[p].r].sum;
}
void update(ll& p, ll pre, ll l, ll r, ll L, ll R, ll d){
    p = ++cnt;
    tree[p] = tree[pre];
    tree[p].sum += (min(r, R) - max(l, L) + 1) * d; //要把子节点标记的影响算进来，有点类似pushup。这里要在if之前，可以自己想一下。
    if(l >= L && r <= R){
        tree[p].add += d; //直接累加标记
        return;
    }
    ll mid = (l+r)>>1;
    if(L <= mid) update(tree[p].l, tree[pre].l, l, mid, L, R, d);
    if(R > mid) update(tree[p].r, tree[pre].r, mid+1, r, L, R, d);
}
ll query(ll p, ll l, ll r, ll L, ll R, ll add){
    if(L <= l && r <= R){
        return tree[p].sum + (r-l+1)*add;
    }
    ll ans = 0;
    add += tree[p].add; //这里却不用放在if上面，可以想想为什么
    ll mid = (l+r)>>1;
    if(L <= mid) ans += query(tree[p].l, l, mid, L, R, add);
    if(R > mid) ans += query(tree[p].r, mid+1, r, L, R, add);
    return ans;
}
int main(){
    ios::sync_with_stdio (0);
    cin.tie(0), cout.tie(0);
    ll n,m;
    cin>>n>>m;    
    for(ll i = 1; i <= n; i++){
        cin>>a[i];
    }
    build(head[0], 1, n);
    ll t = 0;
    ll cur = 0;
    while(m--){
        char op;
        cin>>op;
        if(op == 'C'){  
            ll l,r,d;
            cin>>l>>r>>d;
            t++;
            update(head[t], head[t-1], 1, n, l, r, d);
        }else if(op == 'Q'){
            ll l,r;
            cin>>l>>r;
            cout<<query(head[t], 1, n, l, r, 0)<<endl;
        }else if(op == 'H'){
            ll l,r,t;
            cin>>l>>r>>t;
            cout<<query(head[t], 1, n, l, r, 0)<<endl;
        }else{
            cin>>t;
        }
    }
    return 0;
}

标记永久化原理

在update函数中，我们直接将标记打在节点上，并计算子节点标记的影响，类似于pushup操作。在query函数中，我们把一路上的标记影响累加下来，最后一起计算，类似于pushdown操作。

总结来说，sum字段记录了考虑节点变化后的节点和，但由于父节点的修改信息未知，需要在查询时将父节点的修改带下来。