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

· · 题解

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

可持久化数据结构是算法竞赛中的重要知识点，它允许我们在修改数据的同时保留历史版本。本题要求解决静态区间第 k 小值问题，是可持久化权值线段树（主席树）的经典应用场景。

问题分析

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

算法思路

可持久化权值线段树的核心思想是：对于每个前缀 [1..i]，维护一棵权值线段树，记录该前缀中每个数值出现的次数。当需要查询区间 [l..r] 时，我们可以通过前缀和的思想，用第 r 棵树减去第 l-1 棵树，得到区间 [l..r] 的权值线段树，进而快速查询第 k 小值。

具体步骤如下：

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

代码实现

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

#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;
}
/*
*注释&笔记:无
*样例输入:

*样例输出:

*/

代码解释

  1. 离散化处理：通过将原数组排序并去重，将每个元素映射到一个连续的整数区间，大大减少了线段树的空间复杂度。

  2. 可持久化权值线段树：每个节点包含左右子节点指针和元素计数。每次插入操作都会生成一个新节点，并复用大部分未修改的节点，从而高效地保留历史版本。

  3. 查询操作：利用前缀和思想，通过 root[r] 和 root[l-1] 两棵树的差异，快速定位区间 [l..r] 的第 k 小值。查询过程中，根据左子树的元素个数决定往左还是往右递归，时间复杂度为 O(\log n)。

复杂度分析

感谢@whoseJam的讲解