最详细的静态主席树讲解

I.基础

主席树总的来说就是权值线段树的一种变法,也就是一种非主流的线段树。所以我们需要对线段树有深刻理解。光光AC线段树1和线段树2是远远不够的。以下推荐这几个材料:

1.Blog 这篇博客感觉还是不错,特别就是后面的几个知识点,是一个线段树的扩张。

2.权值线段树简单了解以下。

3.Luogu 1801尽量用权值线段树做,不要用堆。

4.推荐一道水题 Alice的游戏,题目原链接:攒送们

II.前言/背景

背景

为什么叫主席树?这可能是很多人的疑问。

如果我没有记错,应该就是第23个人,网页。

没错,他就叫黄嘉泰,那么把拼音取出来:hjt。就是我们伟大的主席。

前言

1.先致谢几个大佬:

  • 洛谷所有写了题解的大佬
  • ZJJ和GSM大佬
  • 远航休息站

2.此篇博客没有任何政治主张

3.主席树就是一个垃圾回收的权值线段树,其实很简单,实现由一点难。(建议改为普及+ ~ 提高-)

III.权值线段树 - 做区间第k大

好了废话完了,我们步入正题。如果你已经做完,看完了上面的基础部分,那么已经知道这道题的部分做法了,我这里就重新讲解权值线段树。

权值线段树很简单,它的点维护的只是值出现的次数。什么意思?看图:

这个很容易理解,那么我们怎样求第K大呢。步骤

1
2
1.我到达了这个节点,如果左儿子的权值<k,那么说明k不在左子树,往右走,并K值减去左儿子的权值。
2.如果左儿子的权值>=k,k一定在左子树里面,直接往左走。

就是这样:

但是它要求的是区间第k大,怎么办?

我们保存每一次数值修改后的线段树,然后查找u,v这个区间的时候,就可以对两颗线段树进行点对点相减。然后塑造一个”差分后的线段树“,对它进行如上操作。

假如我们要求以上数据的2~4区间第2大,就是这样子的

然后求出第k大就可以了。

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
function Find(l,r:longint):longint; //返回寻找的值
var
        dix,mid:longint; //dix是两颗线段树的相差
begin
        if l=r then //答案
                exit(diss[l]);

        dix:=node[left[node_2]]-node[left[node_1]]; //差分

        mid:=(l+r) div 2;
        if dix>=k then //往左边走
        begin
                node_1:=left[node_1]; //两颗线段树节点一起往左
                node_2:=left[node_2];
                Find:=Find(l,mid); //递归
        end;

        if dix<k then //往右边
        begin
                dec(k,dix);
                node_1:=right[node_1];
                node_2:=right[node_2];
                Find:=Find(mid+1,r);
        end;
end;

IV.空间压缩·垃圾回收

那么多线段树,不卡死你才怪。

我们会发现,这里修改的时候就只有一个log(一条链)的会修改!那我们就可以垃圾回收了!!!

我们要知道什么是改变,什么是垃圾。

这个需要贴一下代码:

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
procedure Query(l,r,key:longint); //左右区间,key是修改的点的编号,上图的修改的点的编号就是2,第2个。
var
        mid:longint;
begin
		//注:now就是前一个历史线段树
        inc(cnt); //动态开点
        node[cnt]:=node[now]+1; //直接
        if l=r then //到了叶子节点
                exit;
        mid:=(l+r) div 2; //中间
        if key<=mid then //往左边建立新的节点
        begin
                left[cnt]:=cnt+1; //新节点的左儿子绝对是cnt+1,思考
                right[cnt]:=right[now]; //右边是历史线段树的右边,垃圾回收
                now:=left[now]; //往左
                Query(l,mid,key); //往左
        end;
        if key>mid then //往右边建立新的节点
        begin
                right[cnt]:=cnt+1; //同上
                left[cnt]:=left[now];
                now:=right[now];
                Query(mid+1,r,key);
        end;
end;

顺便一提,权值线段树+垃圾回收=主席树。

VI.离散化

我不知道我会不会真正的离散化,但是我是这样子做的:

1
2
3
4
1.给每第i个数字给一个编号i。
2.排序,要把编号一起转换。
3.去掉重复,给予线段树编号
4.再开一个桶,存储此主席树编号对应的原数组的数是什么。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
procedure ready;
var
        dis_:longint;
begin
        dis_:=0;
        read(n,m);
        for i:=1 to n do
        begin
                read(num[i]); //值
                place[i]:=i; //原数组编号
        end;
        Sort(1,n); //排序
        num[0]:=-1000000007; //血的教训
        for i:=1 to n do
        begin
                if num[i]<>num[i-1] then //去重
                        inc(dis_);
                dis[place[i]]:=dis_; //原数组的数字的主席树编号是
                diss[dis[place[i]]]:=num[i]; //主席树的编号对应的原数组
        end;
        dis_num:=dis_; //去重后的数字个数
end;

如果我们找到了l=r,也就是答案,那么就直接输出:

1
writeln(diss[l(或者是r,没有关系)]);

VII.存储结构/动态开点

我们不能用树的性质来存储节点,索性就直接存储。如果我们需要开启一个新的节点,包括几个东西:

1
2
3
1.node 节点的权值
2.left 左儿子的位置
3.right 右儿子的位置

注意一下就可以了。

1
2
1.修改(query)的时候,因为下一个点肯定就是cnt+1,直接赋值(左儿子或右儿子)。
2.Build了解一下

VIII.Build

一开始我们要建造一个空的线段树,为什么?因为有事后会玄学WA。但是本题目不用,还能省掉很多时间复杂度。贴代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function Build(l,r:longint):longint; //Build返回的是儿子的节点
var
        mid,now:longint;
begin
        inc(cnt); //动态开点
        now:=cnt; //存储现在节点的位置
        node[now]:=0; //就是空树

        if l=r then //叶子
                exit(now);

        mid:=(l+r) div 2;
        left[now]:=Build(l,mid); //左儿子节点
        right[now]:=Build(mid+1,r); //右儿子节点
        exit(now); //返回本节点编号,递归思想
end;

IX.安利/CODE

顺便安利一下我的个拓本博客:传送门,感觉还是不错的。

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
//上面已经讲了很多,不再加注释。
//如果想快一点,把Build删掉。

// luogu-judger-enable-o2

var
        left,right,node:array[-1..4000440] of longint;
        num,root:array[-1..200100] of longint;
        place,dis,diss:array[-1..200100] of longint;
        i,j,n,m,u,v,k,cnt,now,t,d,dis_num:longint;
        node_1,node_2:longint;

procedure Sort(l,r:longint);
var
    i,j,s,t:longint;
begin
    i:=l; j:=r; s:=num[(l+r) div 2];
        repeat
                while num[i]<s do inc(i);
                while num[j]>s do dec(j);
                if i<=j then
                begin
                        t:=num[i]; num[i]:=num[j]; num[j]:=t;
                        t:=place[i]; place[i]:=place[j]; place[j]:=t;
                inc(i); dec(j);
                end;
        until i>=j;
        if i<r then Sort(i,r);
        if j>l then Sort(l,j);
end;

procedure ready;
var
        dis_:longint;
begin
        dis_:=0;
        read(n,m);
        for i:=1 to n do
        begin
                read(num[i]);
                place[i]:=i;
        end;
        Sort(1,n);
        num[0]:=-1000000007;
        for i:=1 to n do
        begin
                if num[i]<>num[i-1] then
                        inc(dis_);
                dis[place[i]]:=dis_;
        end;
        for i:=1 to n do
                diss[dis[place[i]]]:=num[i];
        dis_num:=dis_;
end;

function Build(l,r:longint):longint;
var
        mid,now:longint;
begin
        inc(cnt);
        now:=cnt;
        node[now]:=0;

        if l=r then
                exit(now);

        mid:=(l+r) div 2;
        left[now]:=Build(l,mid);
        right[now]:=Build(mid+1,r);
        exit(now);
end;

procedure Query(l,r,key:longint);
var
        mid:longint;
begin
        inc(cnt);
        node[cnt]:=node[now]+1;

        if l=r then
                exit;

        mid:=(l+r) div 2;
        if key<=mid then
        begin
                left[cnt]:=cnt+1;
                right[cnt]:=right[now];
                now:=left[now];
                Query(l,mid,key);
        end;

        if key>mid then
        begin
                right[cnt]:=cnt+1;
                left[cnt]:=left[now];
                now:=right[now];
                Query(mid+1,r,key);
        end;
end;

function Find(l,r:longint):longint;
var
        dix,mid:longint;
begin
        if l=r then
                exit(diss[l]);

        dix:=node[left[node_2]]-node[left[node_1]];

        mid:=(l+r) div 2;
        if dix>=k then
        begin
                node_1:=left[node_1];
                node_2:=left[node_2];
                Find:=Find(l,mid);
        end;

        if dix<k then
        begin
                dec(k,dix);
                node_1:=right[node_1];
                node_2:=right[node_2];
                Find:=Find(mid+1,r);
        end;
end;

procedure Chair_Tree;
var
        i,j:longint;
begin
        Build(1,dis_num);

        for i:=1 to n do
        begin
                root[i]:=cnt+1;
                now:=root[i-1];
                Query(1,dis_num,dis[i]);
        end;

        for i:=1 to m do
        begin
                read(u,v,k);
                node_1:=root[u-1];
                node_2:=root[v];
                writeln(Find(1,dis_num));
        end;
end;

begin
        Ready;
        Chair_Tree;
end.

7/15 更新

最近看到一些静态主席树的题目。我们知道静态主席树不仅仅可以做”可持久化线段树”,而且还可以做”可持久化数组”,而时间、空间复杂度都不会比想出来如何用其他数据结构来做”可持久化数组”慢、大非常非常多,并且非常可观。

所以我这里有一道例题,大家脑AC吧:

3794. 【NOIP2014模拟8.20】高级打字机 (Standard IO)

Description

1
2
3
4
5
早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。
请为这种高级打字机设计一个程序，支持如下3种操作：
T x：在文章末尾打下一个小写字母x。(type操作)
U x：撤销最后的x次修改操作。（Undo操作）（注意Query操作并不算修改操作）
Q x：询问当前文章中第x个字母并输出。（Query操作）文章一开始可以视为空串。

Input

1
2
第1行：一个整数n，表示操作数量。
以下n行，每行一个命令。保证输入的命令合法。

Output

1
每行输出一个字母，表示Query操作的答案。

Sample Input / Output

1
2
3
4
5
6
7
8
7
T a
T b
T c
Q 2
U 2
T c
Q 2
1
2
b
c

使用主席树来维护”可持久化数组”,具体思路和k-th number不大一样,可是主要结构是一样的。

Code

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
79
var
        n,cnt,hao,tot:longint;
        len,lson,rson,root:array[0..2000035] of longint;
        value:array[0..2000035] of char;
        s:string;
        HuHa:char;

procedure build(var rt:longint; fa,l,r,po:longint);
var
        mid:longint;
begin
        if (rt=0) then
        begin
                inc(tot);
                rt:=tot;
        end;
        if l=r then
        begin
                value[rt]:=HuHa;
                exit;
        end;

        mid:=(l+r) div 2;
        if (po<=mid) then
        begin
                rson[rt]:=rson[fa];
                build(lson[rt],lson[fa],l,mid,po);
        end;
        if (po>=mid+1) then
        begin
                lson[rt]:=lson[fa];
                build(rson[rt],rson[fa],mid+1,r,po);
        end;
end;

function Query(rt,l,r,po:longint):char;
var
        mid:longint;
begin
        if l=r then
                exit(value[rt]);
        mid:=(l+r) div 2;
        if (po<=mid) then
                exit(Query(lson[rt],l,mid,po));
        if (po>=mid+1) then
                exit(Query(rson[rt],mid+1,r,po));
end;

begin
        readln(n);
        while n>0 do
        begin
                readln(s);
                if s[1]='T' then
                begin
                        HuHa:=s[3];
                        inc(cnt);
                        len[cnt]:=len[cnt-1]+1;
                        Build(root[cnt],root[cnt-1],1,100007,len[cnt]);
                end;

                if s[1]='U' then
                begin
                        delete(s,1,2);
                        val(s,hao);
                        inc(cnt);
                        len[cnt]:=len[cnt-hao-1];
                        root[cnt]:=root[cnt-hao-1];
                end;

                if s[1]='Q' then
                begin
                        delete(s,1,2);
                        val(s,hao);
                        writeln(Query(root[cnt],1,100007,hao));
                end;
                dec(n);
        end;
end.