本文介绍动态主席树，学习之前，你必须需要先了解静态主席树，本文只介绍相对于静态主席树多出来的部分。
动态主席树已经算是另一种数据结构了。这里以ZOJ2112为例。
首先我们需要知道主席树是一种离线数据结构，意思是我们不能一边询问一边修改或输出。所以我们把询问存储起来，这里主要是因为我们要储存改变的值，不然无法离散化，所以就离线了。这里要改变一个值，例如把2变成6，那么2的数量就要少一个，6的数量就要多一个，可我们又不能再开一个线段树，所以我们考虑将每一个节点都变成一棵树，每对他进行操作时就是对这棵树进行操作。下面给出详细代码及其注释。
#pragma GCC optimize(2)
#include <algorithm>
#include <iostream>
#include <cstdio>
#define sc(a) scanf("%d", &a)
#define _ff(i, a, b) for (int i = (a); i <= (b); ++i)
#define lowbit(x) x&(-x)
using namespace std;
//由于是离线操作，线段树最多有(N+询问的个数)棵
const int maxn = 6e4 + 5;
const int maxm = 1e4 + 5;
const int maxk = maxn * 32;
//a数组为初始数组，b数组用来离散化
int a[maxn], b[maxn];
//rt数组记录每棵主席树根节点的下标
int sum[maxk], ls[maxk], rs[maxk], rt[maxn];
int num, n, tot;
/*
树状数组ta每个节点记录的是每棵线段树的根节点
ul数组记录询问区间下界的节点下移，ur数组记录询问区间上界的节点下移
*/
int ta[maxn], ul[maxn], ur[maxn];
struct Query{
int l, r, k;
bool flag;
}q[maxm];
void build(int &node, int l, int r) {
node = ++tot;
sum[node] = 0;
if (l == r) return;
int mid = (l + r) >> 1;
build(ls[node], l, mid);
build(rs[node], mid + 1, r);
}
void update(int &node, int pre, int l, int r, int pos, int val) {
node = ++tot;
sum[node] = sum[pre] + val;
ls[node] = ls[pre], rs[node] = rs[pre];
if (l == r) return;
int mid = (l + r) >> 1;
if (pos <= mid) update(ls[node], ls[pre], l, mid, pos, val);
else update(rs[node], rs[pre], mid + 1, r, pos, val);
}
//传入的是在初始数组里的下标
void add(int x, int val) {
//记录其在离散化数组里的下标
int pos = lower_bound(b + 1, b + 1 + num, a[x]) - b;
/*
这里注意主席树每棵线段树的根节点的下标对应的值与初始数组a下标对应的值是一样的
因为主席树的构建是按照初始数组的顺序构造的
*/
for (; x <= n; x += lowbit(x)) update(ta[x], ta[x], 1, num, pos, val);
}
//查找x位置的前缀和，f为真代表查找上界，f为假查找下界
int getsum(int x, bool f) {
int res = 0;
for (; x; x -= lowbit(x)) {
if (f) res += sum[ls[ur[x]]];
else res += sum[ls[ul[x]]];
}
return res;
}
/*
st代表询问区间的下界、ed代表询问区间的上界
stpos代表第st棵线段树的根节点、edpos代表第ed棵线段树的根节点
*/
int query(int st, int ed, int stpos, int edpos, int l, int r, int pos) {
if (l == r) return l;
/*
利用前缀和求区间和，分别计算权值线段树（构成主席树的每棵线段树都是一棵权值线段树）和树状数组
只需要计算左区间里数字的个数，如果pos小于等于左区间的数字的个数，则去查找左区间，反之查找右区间，
查找右区间时，对应的pos要减去左区间数字的个数，因为找的是整个区间的第k个数。
*/
int tmp = sum[ls[edpos]] - sum[ls[stpos]] + getsum(ed, true) - getsum(st, false);
int mid = (l + r) >> 1;
if (pos <= tmp) {
//查找的点在左区间
//树状数组的节点跟随主席树的节点下移
for (int i = ed; i; i -= lowbit(i)) ur[i] = ls[ur[i]];//上界下移
for (int i = st; i; i -= lowbit(i)) ul[i] = ls[ul[i]];//下界下移
return query(st, ed, ls[stpos], ls[edpos], l, mid, pos);
} else {
//查找的点在右区间
//同上
for (int i = ed; i; i -= lowbit(i)) ur[i] = rs[ur[i]];
for (int i = st; i; i -= lowbit(i)) ul[i] = rs[ul[i]];
return query(st, ed, rs[stpos], rs[edpos], mid + 1, r, pos - tmp);
}
}
signed main() {
// freopen("a.in", "r", stdin);
char op[5]; int cntb, lbw, Q;
int kase; sc(kase);
while (kase--) {
cntb = 0, tot = 0; sc(n), sc(Q);
_ff(i, 1, n) {
sc(a[i]);
b[++cntb] = a[i];
}
//主席树是离线的，这也是他的局限所在。
_ff(i, 1, Q) {
scanf("%s", op);
if (op[0] == ‘C‘) {
scanf("%d%d", &q[i].l, &q[i].r);
q[i].flag = false;
b[++cntb] = q[i].r;
} else {
scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);
q[i].flag = true;
}
}
sort(b + 1, b + 1 + cntb);
num = unique(b + 1, b + 1 + cntb) - b - 1;
build(rt[0], 1, num);
_ff(i, 1, n) {
lbw = lower_bound(b + 1, b + 1 + num, a[i]) - b;
update(rt[i], rt[i - 1], 1, num, lbw, 1);
}
_ff(i, 1, n) ta[i] = rt[0];
_ff(i, 1, Q) {
if (q[i].flag) {
//flag为真代表查询
//查询并记录查询上界和下界的根节点
for (int j = q[i].r; j; j -= lowbit(j)) ur[j] = ta[j];
for (int j = q[i].l - 1; j; j -= lowbit(j)) ul[j] = ta[j];
//查询返回的是其在离散数组里的下标
int ans = query(q[i].l - 1, q[i].r, rt[q[i].l - 1], rt[q[i].r], 1, num, q[i].k);
printf("%d\n", b[ans]);
} else {
//把x变成y，相当于删去一个x，增加一个y，此消彼长
add(q[i].l, -1);
a[q[i].l] = q[i].r;
add(q[i].l, 1);
}
}
}
return 0;
}
原文：https://www.cnblogs.com/xdaniel/p/13458543.html