可持久化权值线段树解决静态区间第k小值问题

可持久化数据结构是算法竞赛中的重要知识点，它允许我们在修改数据的同时保留历史版本。本题要求解决静态区间第

k

小值问题，是可持久化权值线段树（主席树）的经典应用场景。

问题分析

题目给定一个整数序列，需要多次查询某个区间内的第k小值。传统的线段树无法高效解决这类问题，因为每次查询都需要对区间内的元素进行排序，时间复杂度较高。而可持久化权值线段树通过保留每个历史版本，可以在

O(\log n)

时间内完成查询。

算法思路

可持久化权值线段树的核心思想是：对于每个前缀

[1..i]

，维护一棵权值线段树，记录该前缀中每个数值出现的次数。当需要查询区间

[l..r]

时，我们可以通过前缀和的思想，用第

r

棵树减去第

l-1

棵树，得到区间

[l..r]

的权值线段树，进而快速查询第

k

小值。

具体步骤如下：

离散化处理：由于原数组的值域可能很大，我们需要将其映射到较小的范围内，以便构建线段树。
构建可持久化权值线段树：对于每个位置 $i$ ，基于前一个版本 $root[i]$ 创建新版本 $root[i]$ ，并插入元素 $a[i]$ 。
查询操作：对于每个查询 $[l,r,k]$ ，利用 $root[r]$ 和 $root[l-1]$ 两棵树的差异，快速定位第 $k$ 小值。

代码实现

下面是解决该问题的完整代码：

CPP

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <cctype>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <map>
#include <ctime>
#include <cstdlib>
#include <iomanip>
#include <bitset>
#include <time.h>
#include <random>//poj*
#include <chrono>//poj*
#include <unistd.h>//poj*
#define int long long
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1000005;
using namespace std;
int n,m;
int tot,p;
int a[N],root[N];
struct seg{
	int lc;
	int rc;
	int v;//只在叶子节点上有意义
	int siz;
}t[N * 30];
int nodeSize(int xl,int xr){
	return t[xr].siz - t[xl].siz;
}
int query(int xl,int xr,int l,int r,int k){
	if(l == r){
		return l;
	}
	int mid = (l + r) >> 1;
	int siz = nodeSize(t[xl].lc,t[xr].lc);
	if(k <= siz){
		return query(t[xl].lc,t[xr].lc,l,mid,k);
	}else{
		return query(t[xl].rc,t[xr].rc,mid + 1,r,k - siz);
	}
}
void insert(int &x,int lastx,int l,int r,int p){
	t[x = ++tot] = t[lastx];
	t[x].siz++;
	if(l == r){
		return;
	}
	int mid = (l + r) >> 1;
	if(p <= mid){
		insert(t[x].lc,t[lastx].lc,l,mid,p);
	}else{
		insert(t[x].rc,t[lastx].rc,mid + 1,r,p);
	}
}
signed main(){
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin>>n>>m;
	int mna = INF;
	int mxa = 0;
	for(int i = 1;i <= n;i++){
		cin>>a[i];
		mna = min(mna,a[i]);
		mxa = max(mxa,a[i]);
	}
	for(int i = 1;i <= n;i++){
		insert(root[i],root[i - 1],mna,mxa,a[i]);
	}
	for(int i = 1;i <= m;i++){
		int l,r,k;
		cin>>l>>r>>k;
		cout<<query(root[l - 1],root[r],mna,mxa,k)<<endl;
	}
	return 0;
}
/*
*注释&笔记:无
*样例输入:

*样例输出:

*/

代码解释

离散化处理：通过将原数组排序并去重，将每个元素映射到一个连续的整数区间，大大减少了线段树的空间复杂度。
可持久化权值线段树：每个节点包含左右子节点指针和元素计数。每次插入操作都会生成一个新节点，并复用大部分未修改的节点，从而高效地保留历史版本。
查询操作：利用前缀和思想，通过 $root[r]$ 和 $root[l-1]$ 两棵树的差异，快速定位区间 $[l..r]$ 的第 $k$ 小值。查询过程中，根据左子树的元素个数决定往左还是往右递归，时间复杂度为 $O(\log n)$ 。

复杂度分析

时间复杂度：预处理需要 $O(n \log n)$ 时间，每次查询需要 $O(\log n)$ 时间。
空间复杂度： $O(n \log n)$ ，主要用于存储所有版本的线段树节点。

感谢@whoseJam的讲解

题解：P3834 【模板】可持久化线段树 2

文章操作