1 问题
给定不再修改的数组,多次询问
权值线段树 可以查询整个集合的第
可以借用前缀和的思想:前缀频次相减,得到区间频次。 再用 可持久化线段树 保存全部前缀版本。
2 前缀版本
先离散化全部数值,统一值域为 root[i] 为前
root[0]表示空集合,用空根即可。 root[i]在root[i-1]上插入一个,通过路径复制保存新版本。
版本按前缀长度编号,树上的区间按值域划分,二者不可混淆。
3 两个根之差
对于同一值域区间
两棵树使用同一离散化结果、同一区间划分,因此可以同步访问对应节点。
数组为
这里的“相减”只是在访问时计算两个计数之差,不需要真正构造一棵差分树。
4 第 k 小
同时从 root[l-1]、root[r] 出发,计算当前左半值域中的区间频次:
若
在上例中,
5 正确性
每个前缀版本由前一个版本插入一个元素得到,路径复制保证旧版本不变,所以 root[i] 始终准确表示前
两个前缀嵌套,逐值相减后恰好留下下标
任意两个历史版本未必嵌套,它们的频次差可能为负,不能都这样查第
6 代码
格式对应 luogu P3834: 【模板】可持久化线段树 2:第一行 n m,第二行数组,接下来 l r k,保证
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
typedef long long ll;
const int maxn = 200000 + 5;
// n≤2×10^5,每次插入至多复制 19 个节点,预留 20n。
const int maxnode = maxn * 20;
int n, m, kinds, tot;
// a 保留原数组顺序;values 排序去重后,将值域编号还原为原值。
ll a[maxn], values[maxn];
// root[i] 记录前 i 项的值域频次树;0 号节点表示全零的空树。
int root[maxn], lc[maxnode], rc[maxnode], cnt[maxnode];
// 在旧前缀版本上插入一个值域编号 pos,复制路径并返回新根。
int insert(int old, int l, int r, int pos) {
assert(tot + 1 < maxnode);
int p = ++tot;
// 复制两个孩子编号;稍后只替换包含 pos 的孩子,另一侧继续共享。
lc[p] = lc[old];
rc[p] = rc[old];
cnt[p] = cnt[old] + 1; // 插入值属于当前值域,总次数增加 1
if (l == r) return p;
int mid = l + (r - l) / 2;
if (pos <= mid) lc[p] = insert(lc[old], l, mid, pos);
else rc[p] = insert(rc[old], mid + 1, r, pos);
return p;
}
// before 是目标下标区间之前的前缀根,now 是其右端点处的前缀根。
// [l,r] 是当前值域;两棵树同步向下,用频次之差统计目标区间。
int kth(int before, int now, int l, int r, int k) {
if (l == r) return l; // 得到值域编号,还需用 values 还原数值
int mid = l + (r - l) / 2;
int left_count = cnt[lc[now]] - cnt[lc[before]]; // 目标区间落在左半值域的次数
if (k <= left_count) return kth(lc[before], lc[now], l, mid, k);
// 跳过左边的 left_count 个数,在右边继续找剩余排名。
return kth(rc[before], rc[now], 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];
values[i] = a[i];
}
// 所有前缀共用同一套离散化与区间划分,对应节点才能相减。
sort(values + 1, values + n + 1);
kinds = int(unique(values + 1, values + n + 1) - values - 1);
for (int i = 1; i <= n; ++i) {
int pos = int(lower_bound(values + 1, values + kinds + 1, a[i]) - values);
root[i] = insert(root[i - 1], 1, kinds, pos); // 前 i-1 项再加入 a[i]
}
while (m--) {
int l, r, k;
cin >> l >> r >> k;
// 前 r 项减去前 l-1 项,只留下下标区间 [l,r] 的频次。
int id = kth(root[l - 1], root[r], 1, kinds, k);
cout << values[id] << '\n';
}
return 0;
}
输入:
5 4
2 4 2 1 3
2 5 3
1 3 2
3 3 1
1 5 5
输出:
3
2
2
4
重复值共享一个叶子,但出现次数分别计入排名。
7 复杂度与边界
离散化
模板支持 20 * maxn 个节点,三个 int 节点数组约
本篇处理静态数组。修改一个原数组元素会影响它之后的所有前缀版本,不能只修改某一个根便认为其他版本已经同步。
8 练习
- luogu P3834: 【模板】可持久化线段树 2:检查两个根分别对应
与 。 - 改为查询
中小于等于 的元素个数。 - 增加频次加权和,求区间内最小的
个数之和;进入右边前应先累加左半值域的全部贡献。
9 相关题解
暂无相关题解