主席树学习笔记

前置芝士

• 线段树
• 动态开店线段树
• 权值线段树
• 脑子 pvz 玩多了

用处

主席树即可持久化线段树，在线段树的基础上可以查询修改每个修改的内容并形成新的版本。

思想

如果每次修改后在建一棵线段树，空间复杂度肯定受不了。注意到线段树的一次修改操作最多影响 $\log$ 个节点。因此我们可以只新建修改的节点，将原来的节点也用上，这样空间复杂度就是 $\Theta((n + q) \log n)$ 的。

实现

可持久化数组

给出一个长度为 $n$ 的序列 $a_i$，此时的序列为版本 $0$ ，支持一下两种操作；

• 在一个版本的基础上单点修改，形成一个新的版本；

• 在一个版本的基础上单点查询，形成一个一模一样的新版本。

$1 \le n,q \le 10^6$。

板子题（当然其它方法也很多），就来看看实现。需要动态开点，所以要记录所有儿子的信息：

struct Chairman_tree {
    int ls, rs, s;
    #define lid tr[id].ls
    #define rid tr[id].rs
}tr[N * 32];
int cnt = 0;

初始建树、查询和普通线段树没什么区别，我们来看看修改操作：

int Add(int id, int l, int r, int x, int v) {
    tr[++ cnt] = tr[id], id = cnt;
    // 每次修改后新建节点，复制原节点的信息
    if (l == r) {
        tr[id].s = v; return id;
    }
    int mid = l + r >> 1;
    if (x <= mid) lid = Add(lid, l, mid, x, v);
    if (x > mid) rid = Add(rid, mid + 1, r, x, v);
    // 修改后左右儿子也会改
    return id;
}

// 在主程序中：
v[++ tot] = Add(v[ver], 1, n, x, y); // 修改的同时新建版本

完整代码

#include <bits/stdc++.h>
using namespace std;

inline int read() {
	int x = 0, f = 0; char c = 0;
	while (!isdigit(c)) f |= c == '-', c = getchar();
	while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
	return f ? -x : x;
}

#define N 1000010

int n, m, a[N], v[N], tot;

struct Chairman_tree {
    int ls, rs, s;
    #define lid tr[id].ls
    #define rid tr[id].rs
}tr[N * 32]; int cnt = 0;

void Build(int &id, int l, int r) {
    id = ++ cnt;
    if (l == r) {
        return tr[id].s = a[l], void();
    }
    int mid = l + r >> 1;
    Build(lid, l, mid), Build(rid, mid + 1, r);
}
int Add(int id, int l, int r, int x, int v) {
    tr[++ cnt] = tr[id], id = cnt;
    if (l == r) {
        tr[id].s = v; return id;
    }
    int mid = l + r >> 1;
    if (x <= mid) lid = Add(lid, l, mid, x, v);
    if (x > mid) rid = Add(rid, mid + 1, r, x, v);
    return id;
}
int Ask(int id, int l, int r, int x) {
    if (l == r) return tr[id].s;
    int mid = l + r >> 1;
    if (x <= mid) return Ask(lid, l, mid, x);
    if (x > mid) return Ask(rid, mid + 1, r, x);
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i ++) {
        a[i] = read();
    }

    Build(v[0] = ++ cnt, 1, n);

    for (int i = 1; i <= m; i ++) {
        int ver = read();
        if (read() == 1) {
            int x = read(), y = read();
            v[++ tot] = Add(v[ver], 1, n, x, y);
        } else {
            int x = read();
            printf("%d\n", Ask(v[ver], 1, n, x));
            v[++ tot] = v[ver];
        }
    }
    return 0;
}

但是我听机房巨佬说，这道板子题是没有灵魂的 /jk ，所以我们在来一道有灵魂的：

link

给定一个序列，每次查询一段区间的第 $k$ 小值。

$1 \le n,q \le 2 \times 10^5$，$1 \le a_i \le 10^9$。

巨佬说这个就很有灵魂了。我们建立一棵权值线段树，记录维护区间的数的数量。遍历离散化后的序列，每次在前面插入一个数形成新版本（有点像前缀和），接下来我们考虑查询。

首先考虑查询的区间 $\left[1,x\right]$，在 $x$ 这个点对应版本的线段树上，我们进行查询。怎么查很简单，如果左边的数量小于 $k$ 就进入右子树，否则查左子树。那查询 $\left[l,r\right]$ 就很简单了，还是前缀和的思想，在做查询时同步遍历 $l - 1$ 和 $r$ 两棵线段树，相减就得到了 $\left[l,r\right]$ 区间的信息注入灵魂。

妙啊！

CODE

#include <bits/stdc++.h>
using namespace std;

inline int read() {
    int x = 0, f = 0; char c = 0;
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
    return f ? -x : x;
}

#define N 200010
#define pb push_back

int n, m, a[N], v[N];
vector<int> hs;

struct Chairman_tree {
    int ls, rs, s;
    #define lid tr[id].ls
    #define rid tr[id].rs
}tr[N * 32]; int cnt = 0;

void pushup(int id) {
    tr[id].s = tr[lid].s + tr[rid].s;
}
void Build(int &id, int l, int r) {
    id = ++ cnt;
    if (l < r) {
        int mid = l + r >> 1;
        Build(lid, l, mid);
        Build(rid, mid + 1, r);
        pushup(id);
    }
}
int Add(int id, int l, int r, int x) {
    tr[++ cnt] = tr[id], id = cnt;
    if (l == r) tr[id].s ++;
    else {
        int mid = l + r >> 1;
        if (x <= mid) lid = Add(lid, l, mid, x);
        else rid = Add(rid, mid + 1, r, x);
        pushup(id);
    }
    return id;
}
int Ask(int x, int y, int l, int r, int k) {
    if (l == r) return l;
    else {
        int mid = l + r >> 1, lv = tr[tr[y].ls].s - tr[tr[x].ls].s;
        if (k <= lv) return Ask(tr[x].ls, tr[y].ls, l, mid, k);
        else return Ask(tr[x].rs, tr[y].rs, mid + 1, r, k - lv);
    }
}

int main() {
    n = read(), m = read();
    for (int i = 1; i <= n; i ++) {
        a[i] = read(), hs.pb(a[i]);
    }

    sort(hs.begin(), hs.end());
    unique(hs.begin(), hs.end());
    for (int i = 1; i <= n; i ++) {
        a[i] = lower_bound(hs.begin(), hs.end(), a[i]) - hs.begin() + 1;
    }

    Build(v[0], 1, n);
    for (int i = 1; i <= n; i ++) {
        v[i] = Add(v[i - 1], 1, n, a[i]);
    }

    while (m --) {
        int l = read(), r = read(), k = read();
        printf("%d\n", hs[Ask(v[l - 1], v[r], 1, n, k) - 1]);
    }
    return 0;
}