带修主席树—简介

带修主席树本质其实是树套树，是树状数组修饰的主席树。

主席树仅有“版本”之别，却无修改之说。如果强行修改，那么耗费的时间复杂度是$O(T\log n)$。$T$描述的是当前部分后面还有多少的个“链”需要修改，如果对于一棵正常的主席树而言，修改$i$这个位置，$T=n-(i-1)$。

考虑怎样让它的修改次数减少。

仔细分析，发现主席树维护的其实是前缀和，前缀和有一个微型数据结构十分的擅长，那就是树状数组。于是不妨考虑将树状数组和主席树结合，那么就可以将刚刚的T改成至多$\log n$。

具体来说，就是将原本平行的主席树，变成了树状数组的结构，这样下来就可以只修改比当前节点要高树状数组节点了。

时间复杂度$O(n{\log }^{2}n)$

模板题：P2617 Dynamic Rankings

#include
using namespace std;
const int N = 100005;

struct segment_tree{int v; int ls, rs;}t[N * 400]; //线段树开nlogn大小
struct operation{bool b; int l, r, k; int pos, t;}q[N]; //因为要离散花所以要把所有数据输进来离线搞
int n, m, a[N], o[N << 1], rt[N], len, tot, temp[2][20], cnt[2];
char opt[2];

void Modify(int &x,int l,int r,int pos,int val) //就是一个正常的主席树modify
{
	if(!x) x = ++tot;
	t[x].v += val;
	if(l == r) return ;
	int mid = l + r >> 1;
	if(pos <= mid) Modify(t[x].ls, l, mid, pos, val);
	else Modify(t[x].rs, mid + 1, r, pos, val);
}
void prepare_Modify(int x,int val)
{
	int k = lower_bound(o + 1, o + len + 1, a[x]) - o; //只是离散化处理
	for(int i = x; i <= n; i += i & -i) Modify(rt[i], 1, len, k ,val); //处理出需要修改哪log棵主席树
}
int Query(int l,int r,int k)
{
	if(l == r) return l;
	int mid = l + r >> 1, sum = 0;
	for(int i = 1; i <= cnt[1]; i++) sum += t[t[temp[1][i]].ls].v;
	for(int i = 1; i <= cnt[0]; i++) sum -= t[t[temp[0][i]].ls].v; //将所有的左儿子都减掉
	if(k <= sum)
	{
		for(int i = 1; i <= cnt[1]; i++) temp[1][i] = t[temp[1][i]].ls;
		for(int i = 1; i <= cnt[0]; i++) temp[0][i] = t[temp[0][i]].ls; //所有树状数组都要更新新节点
		return Query(l, mid, k);
	}
	else
	{
		for(int i = 1; i <= cnt[1]; i++) temp[1][i] = t[temp[1][i]].rs;
		for(int i = 1; i <= cnt[0]; i++) temp[0][i] = t[temp[0][i]].rs;
		return Query(mid + 1, r, k - sum);
	}
}
int prepare_Query(int l,int r,int k)
{
	memset(temp, 0, sizeof(temp)); //同修改，处理出需要进行相减操作的是哪log棵主席树
	cnt[0] = cnt[1] = 0;
	for(int i = r; i; i -= i & -i) temp[1][++cnt[1]] = rt[i];
	for(int i = l - 1; i; i -= i & -i) temp[0][++cnt[0]] = rt[i];
	return Query(1, len, k);
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]), o[++len] = a[i];
	for(int i = 1; i <= m; i++)
	{
		scanf("%s", opt);
		q[i].b = (opt[0] == 'Q');
		if(q[i].b) scanf("%d%d%d", &q[i].l, &q[i].r, &q[i].k);
		else scanf("%d%d", &q[i].pos, &q[i].t), o[++len] = q[i].t;
	}
	sort(o + 1, o + len + 1);
	len = unique(o + 1, o + len + 1) - o - 1; //离散 —— 排序 + 去重
	for(int i = 1; i <= n; i++) prepare_Modify(i, 1);
	for(int i = 1; i <= m; i++)
	{
		if(q[i].b) printf("%d\n", o[prepare_Query(q[i].l, q[i].r, q[i].k)]);
		else
		{
			prepare_Modify(q[i].pos, -1); //一加一减，十分的暴力
			a[q[i].pos] = q[i].t;
			prepare_Modify(q[i].pos, 1);
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78