当前位置：首页 > news >正文

可持久化线段树

news 2025/10/1 9:13:39

前言

关于主席树和可持久化线段树的区别

主席树全称是可持久化权值线段树，参见知乎讨论。

关于 \(\log{n}\) 和 \(\log_2{n}\) 的区别

在数学中（尤其是纯数学领域），\(\log{n}\) 通常表示以自然对数 \(e\) 为底的对数，即 \(\ln{n}\)。

在计算机科学中，\(\log{n}\) 通常默认表示以 \(2\) 为底的对数，即 \(\log_2{n}\)，因为计算机科学中很多问题涉及二分法（如分治算法、二叉树等）。

可持久化线段树

【模板】可持久化线段树 1（可持久化数组）

非常经典的可持久化权值线段树入门题——静态区间第 \(k\) 小：【模板】可持久化线段树 2

引入

给定 \(n\) 个整数构成的序列 \(a\)，将对于指定的闭区间 \([l,r]\) 查询其区间内的第 \(k\) 小值。

我们能想到用整体二分或者二分+分块去解决问题；

若直接建立权值线段树，发现是无法解绝问题的，考虑使用主席树，其的主要思想就是：保存权值线段树上每次插入操作时的历史版本，以便查询区间第 \(k\) 小。

解析

我们分析一下，发现每次修改操作修改的点的个数是一样的，只更改了 \(O(\log{n})\) 个结点，形成一条链，也就是说每次更改的结点数等于树的高度。

（例如下图，修改了 \([1,8]\) 中对应权值为 \(1\) 的结点，红色的点即为更改的点）

运用动态开点，保存每个节点的左右儿子编号，在记录左右儿子的基础上，保存插入每个数的时候的根节点就可以实现持久化了。

简化一下问题：求区间 \([1,r]\) 的区间第 \(k\) 小值。直接找到 \(r\) 时的根节点版本，再用权值线段树查找即可。

我们可以发现，主席树统计的信息也满足前缀和的性质，所以只需要用 \([1,r]\) 的信息减去 \([1,l - 1]\) 的信息就得到了区间 \([l,r]\) 的信息。

复杂度

时间复杂度

建树和离散化的时间复杂度都为 \(O(n\log{n})\)，单次插入（只用修改 \(\log{n}\) 个节点）和单次查询时的时间复杂度都是 \(O(\log{n})\) 的，所以总时间复杂度 \(O(n\log{n})\)，并不难理解。

空间复杂度

考虑所有建立的结点的个数，建树有 \(2n - 1\) 个节点，每次插入/修改添加 \(\log{n}\) 个节点，至多添加 \(n\log{n}\) 个点，总共需要的空间为 \(2n - 1 + n\log{n}\)，当 \(n \le 10 ^ 5\) 时，约等于 \(20 \times 10 ^ 5\)；

提示：千万不要吝啬空间（大多数题目中空间限制都较为宽松，因此一般不用担心空间超限的问题）！大胆一点，直接上个 \(2 ^ 5 \times 10 ^ 5\)，接近原空间的两倍。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,a[N],unq[N];
struct Tree {int val;int ls,rs; 
} tree[N<<5];
int id[N],iCnt;
inline void build(int &rt,int l,int r) {rt=++iCnt;if(l==r) return ;int mid=(l+r)>>1;build(tree[rt].ls,l,mid);build(tree[rt].rs,mid+1,r);return ;
}
inline void update(int &rt,int pre,int l,int r,int p) {rt=++iCnt;tree[rt]=tree[pre];tree[rt].val++;if(l==r)return ;int mid=(l+r)>>1;if(p<=mid) update(tree[rt].ls,tree[pre].ls,l,mid,p);if(p>mid) update(tree[rt].rs,tree[pre].rs,mid+1,r,p);return ;
}
inline int query(int nl,int nr,int l,int r,int k) {if(l==r)return unq[l];int x=tree[tree[nr].ls].val-tree[tree[nl].ls].val;int mid=(l+r)>>1;if(x>=k) return query(tree[nl].ls,tree[nr].ls,l,mid,k);if(x<k) return query(tree[nl].rs,tree[nr].rs,mid+1,r,k-x); 
}
signed main() {scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++) {scanf("%lld",&a[i]);unq[i]=a[i];}sort(unq+1,unq+n+1);int num=unique(unq+1,unq+n+1)-unq-1;build(id[0],1,num);for(int i=1;i<=n;i++) {int p=lower_bound(unq+1,unq+num+1,a[i])-unq;update(id[i],id[i-1],1,num,p);}for(int i=1;i<=m;i++) {int l,r,k;scanf("%lld%lld%lld",&l,&r,&k);printf("%lld\n",query(id[l-1],id[r],1,num,k)); }return 0;
}