为每个前缀建立可持久化权值线段树，用两个版本的计数差查询区间第 k 小。
OJ: luogu
题目 ID: P3834
难度:提高+/省选-
标签:主席树可持久化线段树离散化数据结构
日期: 2026-06-22 23:16
题意
给定一个静态数组，多次询问区间 [l,r] 内第 k 小的数。
思路
朴素做法是每次复制 [l,r]，排序后输出第 k 个。
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
// brute.cpp：每个询问复制区间并排序，只适合小数据验证。
const int MAXN = 505;
int n, m;
int a[MAXN];
int temp[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= m; i++) {
int l, r, k;
cin >> l >> r >> k;
int len = 0;
for (int j = l; j <= r; j++) {
len++;
temp[len] = a[j];
}
sort(temp + 1, temp + len + 1);
cout << temp[k] << '\n';
}
return 0;
}朴素做法无法承受 2 * 10^5 级别的数据。因为数组没有修改，可以考虑维护前缀信息。
先把所有数离散化。对每个前缀 1..i 建一棵权值线段树 root[i]，表示每个离散值在这个前缀中出现了多少次。相邻前缀只多一个数，所以 root[i] 可以从 root[i-1] 复制一条路径得到，其余节点共享。
对于询问 [l,r]，区间内的频次等于：
text
root[r] - root[l-1]查询第 k 小时，看左子树中有多少个区间元素：
text
left_count = count(left_child[root[r]]) - count(left_child[root[l-1]])如果 left_count >= k，答案在左值域；否则答案在右值域，并把 k 减去 left_count。递归到叶子后，将离散下标映射回原值即可。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
const int MAXNODE = MAXN * 25;
int n, m;
int a[MAXN], sorted_value[MAXN];
int root[MAXN];
int left_child[MAXNODE], right_child[MAXNODE], tree_count[MAXNODE];
int node_count;
int get_rank_value(int x) {
return lower_bound(sorted_value + 1, sorted_value + n + 1, x) - sorted_value;
}
int build(int l, int r) {
int p = ++node_count;
if (l == r) {
return p;
}
int mid = (l + r) / 2;
left_child[p] = build(l, mid);
right_child[p] = build(mid + 1, r);
return p;
}
int update(int old_root, int l, int r, int pos) {
int p = ++node_count;
left_child[p] = left_child[old_root];
right_child[p] = right_child[old_root];
tree_count[p] = tree_count[old_root] + 1;
if (l == r) {
return p;
}
int mid = (l + r) / 2;
if (pos <= mid) {
left_child[p] = update(left_child[old_root], l, mid, pos);
} else {
right_child[p] = update(right_child[old_root], mid + 1, r, pos);
}
return p;
}
int query_kth(int left_root, int right_root, int l, int r, int k) {
if (l == r) {
return l;
}
int mid = (l + r) / 2;
int left_count = tree_count[left_child[right_root]] - tree_count[left_child[left_root]];
if (k <= left_count) {
return query_kth(left_child[left_root], left_child[right_root], l, mid, k);
}
return query_kth(right_child[left_root], right_child[right_root], mid + 1, r, k - left_count);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sorted_value[i] = a[i];
}
sort(sorted_value + 1, sorted_value + n + 1);
int value_count = unique(sorted_value + 1, sorted_value + n + 1) - sorted_value - 1;
root[0] = build(1, value_count);
for (int i = 1; i <= n; i++) {
int pos = lower_bound(sorted_value + 1, sorted_value + value_count + 1, a[i]) - sorted_value;
root[i] = update(root[i - 1], 1, value_count, pos);
}
for (int i = 1; i <= m; i++) {
int l, r, k;
cin >> l >> r >> k;
int rank_pos = query_kth(root[l - 1], root[r], 1, value_count, k);
cout << sorted_value[rank_pos] << '\n';
}
return 0;
}复杂度
离散化和建树总时间
空间复杂度
总结
主席树解决静态区间第 k 小的关键是“前缀版本差分”。两个版本相减后，就得到区间内每个值域段的出现次数。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
