【笔记】可持久化线段树(主席树)

Part 1 简介

可持久化线段树(在中国国内信息学竞赛社区中又称总书记树主席树函数式线段树)是一种可持久化数据结构(Persistent data structure). 由于引入者黄嘉泰姓名的缩写与前中共中央总书记、国家主席胡锦涛相同,因此这种数据结构也可被称为总书记树主席树。这种数据结构在普通线段树的基础之上支持查询某个历史版本,同时时间复杂度与线段树是同级,空间复杂度相较而言更高。

Part 2 应用

静态区间第k大数值

这类问题需要求解在一个长度为$ {\displaystyle n}$ 的数列中,第$ {\displaystyle i} $个数为$ {\displaystyle a_{i}}$. 现在给定一些形如 ${\displaystyle (l,r,k)} $的三元组作为询问,设计程序计算数列第$ {\displaystyle l~r} $这些元素中出现次数排在第$ {\displaystyle k} $位的是多少。

利用可持久化线段树,维护区间$ {\displaystyle (l,r)} $代表区间$ {\displaystyle [l,r]} $中的元素出现了多少次,以此作为原始版本$ {\displaystyle S_{0}}$,此后每次建立一个新版本 ${\displaystyle S_{i}}$,代表去掉原数列中 ${\displaystyle a_{0}~a_{i-1}} $的元素之后建立的线段树,维护目标与上述相同。具体过程可以每次将$ {\displaystyle a_{i}}$的出现次数减一,并保存此时生成的新版本。

Part 3 代码实现

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>

#define MAX_N 200005
using namespace std;

int tot, n, m;
int sum[(MAX_N << 5) + 10], rt[MAX_N + 10], leftson[(MAX_N << 5) + 10], rightson[(MAX_N << 5) + 10];
int a[MAX_N + 10], ind[MAX_N + 10], len;
int l, r, k;

//查找最小下标的匹配值
int getid(const int &val) { return lower_bound(ind + 1, ind + len + 1, val) - ind; }

int build(int l, int r) {
    int root = ++tot;
    if (l == r) return root;
    int mid = (l + r) >> 1;
    leftson[root] = build(l, mid);
    rightson[root] = build(mid + 1, r);
    return root;
} //建树

//节点k代表区间[l,r]
//插入操作
int update(int k, int l, int r, int root) {
    int dir = ++tot;
    leftson[dir] = leftson[root], rightson[dir] = rightson[root], sum[dir] = sum[root] + 1; //新节点
    if (l == r) {
        //sum[dir] = t; 如果题目要求sum加t,去掉注释然后去掉上面的+1
        return dir;
    } //递归底层返回新节点编号,修改父节点的儿子指向
    int mid = (l + r) >> 1;
    if (k <= mid)
        leftson[dir] = update(k, l, mid, leftson[dir]);
    else
        rightson[dir] = update(k, mid + 1, r, rightson[dir]);
    //sum[dir] = sum[lc[dir]] + sum[rightson[dir]];在该题中,不需要这样做,但是很多情况下是要这样更新的
    return dir;
}

//初始的u和v分别代表的是点l-1和点r,l和r分别表示线段树点代表的区间,初始的k表示查询第k小
//查询(历史区间和)
int section_ask(int u, int v, int l, int r, int k) {
    int mid = (l + r) >> 1;
    int x = sum[leftson[v]] - sum[leftson[u]]; //左儿子的信息
    //因为主席树是区间统计好了的,只要减一下即可,无需递归到叶子再处理
    if (l == r) return l; //找到目标位置
    if (k <= x) //说明在左儿子中
        return section_ask(leftson[u], leftson[v], l, mid, k);
    else //说明在右儿子中
        return section_ask(rightson[u], rightson[v], mid + 1, r, k - x);
}

void init() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);

    memcpy(ind, a, sizeof ind);
    sort(ind + 1, ind + n + 1);
    len = unique(ind + 1, ind + n + 1) - ind - 1;
    rt[0] = build(1, len);

    for (int i = 1; i <= n; i++) rt[i] = update(getid(a[i]), 1, len, rt[i - 1]);
}

void work() {
    while (m--) {
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", ind[section_ask(rt[l - 1], rt[r], 1, len, k)]);
    }
}

int main() {
    init();
    work();
    return 0;
}

参考:

可持久化线段树 - 维基百科,自由的百科全书


  目录