可持久化线段树（主席树）

lbh666 · 2025-02-19 23:46:30 · 算法·理论

省流：主要思想：离散化，前缀和，动态开点和线段树上二分。

模板题：P3834。

大体思想

一看到区间问题，首先会想到线段树。但是一棵线段树无法维护区间第 k 小。

• 那如果有多棵呢？我们想到，对于一棵线段树的情况，可以用权值线段树然后线段树上二分解决。即对于一个固定的区间，我们可以使用上述做法，当然离散化缩小值域到 \mathcal O(n) 是必要的。
• 容易发现，[l,r] 所维护的信息等于 [1,r] 所维护的信息减去 [1,l-1] 所维护的信息。
• 自然想到前缀和，所以我们引入权值树的加法：两棵结构相同的线段树每个相应节点作加法，将结果保存在新的一棵结构相同的线段树的对应位置上。减法同理。
• 于是，根据上述探究，不妨开 n 棵线段树，每棵线段树维护 [1,i] 的区间信息。
• 这样，我们就高效完成了区间 [l,r] 信息的维护，做一个线段树上二分就可以了。

动态开点

虽然时间复杂度很不错，为 \mathcal O((n + m) \log n)，但是空间复杂度很劣，为 \mathcal O(n^2)。

考虑优化。我们第 i 棵线段树的信息需要靠第 i-1 棵线段树去维护，其中被修改的叶子节点只有 1 个，所以真正与第 i-1 棵线段树的不同位置构成了一条链，数量为 \mathcal O(\log n)。

动态开点的本质是将没有发生改动的节点进行重复利用，从第 i 棵线段树的节点连到第 i-1 棵线段树的这些节点。

每次新增节点至多增加 \mathcal O(\log n) 个，故此时空间复杂度为 \mathcal O(n \log n)。

小细节：最开始可以建一棵完整的空权值线段树也可以不建，因为最后那些没有用到的节点权值为 0，不建不会影响最终答案。

模板题代码

#include<bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
using namespace std;

const int N=2e5+5;
int n,m,tot=0,sz;
int a[N],b[N],rt[N];

struct tree{
    int l,r,val;
}t[N<<5];

int change(int u,int l,int r,int x){
    int p=++tot;
    int mid=(l+r)>>1;
    t[p].val=t[u].val+1;
    if(l<r){
        if(x<=mid){
            t[p].r=t[u].r;
            t[p].l=change(t[u].l,l,mid,x);
        }else{
            t[p].l=t[u].l;
            t[p].r=change(t[u].r,mid+1,r,x);
        }
    }
    return p;
}

int query(int u,int v,int l,int r,int k){
    if(l==r)return l;
    int sum=t[t[v].l].val-t[t[u].l].val;
    int mid=(l+r)>>1;
    if(k<=sum)return query(t[u].l,t[v].l,l,mid,k);
    return query(t[u].r,t[v].r,mid+1,r,k-sum);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    rep(i,1,n){
        cin>>a[i];
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    sz=unique(b+1,b+n+1)-b-1;
    rep(i,1,n){
        int x=lower_bound(b+1,b+sz+1,a[i])-b;
        rt[i]=change(rt[i-1],1,sz,x);
    }
    while(m--){
        int l,r,k;
        cin>>l>>r>>k;
        int sum=query(rt[l-1],rt[r],1,sz,k);
        cout<<b[sum]<<"\n";
    }
    return 0;
}

关于可持久化线段树的补充（deepseek）

可持久化线段树（Persistent Segment Tree）之所以称为“可持久化”，是因为它能够保留所有历史版本，并在每次修改后生成一个新版本，同时允许高效地访问和查询任意历史版本的数据。以下是其核心原理：

1. 核心思想：路径复制与共享

• 普通线段树的局限性：在传统线段树中，每次修改操作会直接覆盖原节点，导致历史版本被破坏。
• 可持久化的实现：
  当修改某个节点时，可持久化线段树会复制从根到目标节点的整条路径，并在复制的路径上进行修改，而原路径保持不变。未受修改的分支仍直接引用旧节点，从而复用未修改的子树（如图1所示）。

2. 关键特性

• 版本管理：每次修改生成一个新的根节点，不同版本通过不同根节点区分。
• 空间高效：每次修改仅复制路径上的节点（共 \mathcal O(\log n) 个），而非完整复制整棵树，总空间复杂度为 \mathcal O(m \log n)（m 为操作次数）。
• 时间高效：单次修改和查询的时间复杂度仍为 \mathcal O(\log n)。

3. 应用场景

• 历史版本查询：例如，需要回溯某个时间点的数据状态。
• 区间问题：如静态区间第 k 大数（主席树）、区间修改的版本追踪等。
• 函数式编程：支持无副作用的操作，符合不可变数据结构的理念。

4. 示意图

  版本1根              版本2根
    │                    │
    A                    A'（复制并修改）
   / \                  / \
  B   C               B'   C（共享未修改分支）
 /     \             /     \
D       E           D       E

图1：修改节点 B 时，仅复制路径 A \rightarrow B \rightarrow D，生成新节点 A'、B'，而 C 和 E 未被修改，直接共享。

5. 总结

可持久化线段树通过路径复制和节点共享，在保证高效操作的同时保留所有历史版本，从而实现了“可持久化”。这种设计在算法优化和特定问题场景（如离线查询、版本控制）中具有重要价值。

函数式编程的简单概念（deepseek）

函数式编程（Functional Programming，FP）是一种编程范式，其核心思想是将计算视为数学函数的求值，并强调不可变数据和无副作用的操作。