主席树

1 问题

给定不再修改的数组,多次询问 [l,r][l,r] 中第 kk 小的数。

权值线段树 可以查询整个集合的第 kk 小,但每个询问对应不同子数组。若为每个区间重新插入元素,开销太大。

可以借用前缀和的思想:前缀频次相减,得到区间频次。 再用 可持久化线段树 保存全部前缀版本。

2 前缀版本

先离散化全部数值,统一值域为 [1,V][1,V]。定义 root[i] 为前 ii 个元素的权值线段树,叶子记录每个值出现多少次。

  • root[0] 表示空集合,用空根 00 即可。
  • root[i] 在 root[i-1] 上插入一个 aia_i,通过路径复制保存新版本。

版本按前缀长度编号,树上的区间按值域划分,二者不可混淆。

3 两个根之差

对于同一值域区间 II:

count⁡[l,r](I)=count⁡[1,r](I)−count⁡[1,l−1](I). \operatorname{count}_{[l,r]}(I) =\operatorname{count}_{[1,r]}(I) -\operatorname{count}_{[1,l-1]}(I).

两棵树使用同一离散化结果、同一区间划分,因此可以同步访问对应节点。

第五个前缀减去第一个前缀,得到下标二到五的值域频次

数组为 [2,4,2,1,3][2,4,2,1,3]。查询 [2,5][2,5],从前五项的频次中减去第一项 22 的一次出现,得到 {1,2,3,4}\{1,2,3,4\}。

这里的“相减”只是在访问时计算两个计数之差,不需要真正构造一棵差分树。

4 第 k 小

同时从 root[l-1]、root[r] 出发,计算当前左半值域中的区间频次:

s=cnt[lc[root[r]]]−cnt[lc[root[l−1]]]. s=cnt[lc[root[r]]]-cnt[lc[root[l-1]]].

若 k≤sk\le s,两个根都进入左孩子;否则都进入右孩子,并令 k←k−sk\gets k-s。不断缩小值域,到叶子后还原数值。

在上例中,[1,2][1,2] 有两个数。查询第 33 小时先进入值域 [3,4][3,4],继续找其中第 11 小,得到 33。

5 正确性

每个前缀版本由前一个版本插入一个元素得到,路径复制保证旧版本不变,所以 root[i] 始终准确表示前 ii 项的频次。

两个前缀嵌套,逐值相减后恰好留下下标 [l,r][l,r] 的频次,且各项非负。于是左孩子频次之差就是当前候选集合落在左半值域中的数量。按数量选择左右分支,与普通权值线段树的第 kk 小查找相同,故答案正确。

任意两个历史版本未必嵌套,它们的频次差可能为负,不能都这样查第 kk 小;区间最大值等信息也不能通过两个前缀最大值相减得到。

6 代码

格式对应 luogu P3834: 【模板】可持久化线段树 2:第一行 n m,第二行数组,接下来 mm 行 l r k,保证 1≤k≤r−l+11\le k\le r-l+1。

#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 复杂度与边界

离散化 O(nlog⁡n)O(n\log n),建立全部前缀版本 O(nlog⁡V)O(n\log V),单次查询 O(log⁡V)O(\log V),节点数 O(nlog⁡V)O(n\log V)。V=1V=1 时插入和查询均为常数时间。

模板支持 n≤2×105n\le2\times10^5,每次插入最多创建 1919 个节点,预留 20 * maxn 个节点,三个 int 节点数组约 4848 MB。空节点的孩子和计数均为零,所有前缀共享这套空子树语义。

本篇处理静态数组。修改一个原数组元素会影响它之后的所有前缀版本,不能只修改某一个根便认为其他版本已经同步。

8 练习

  • luogu P3834: 【模板】可持久化线段树 2:检查两个根分别对应 l−1l-1 与 rr。
  • 改为查询 [l,r][l,r] 中小于等于 xx 的元素个数。
  • 增加频次加权和,求区间内最小的 kk 个数之和;进入右边前应先累加左半值域的全部贡献。

9 相关题解

暂无相关题解