【OI之路】02数据结构-6主席树

6.6.0 背景

对于两颗上下界相同的线段树,其结构唯一,节点一一对应。

至于主席树来历之类的八卦,请自行上网搜索。
某大佬:http://blog.csdn.net/xgc_woker/article/details/78018297

6.6.1 性质

主席树,主要用于解决区间大小关系询问类问题,当然也用到了身为区间问题始祖的前缀和。
其实它本质上是一颗权值线段树,所以比较大小就比较方便啦。

由于它存储的值是,对应某段区间,在他管辖范围内的这些数字总共出现了多少次。
也正是由于出现次数满足可加性,前缀和可以很好的解决。

对于长度为1的一个区间,如果只看有用的信息,
它的形状大致是一根链(空间logn),所以应该看成残缺的线段树
(否则就会需要大量空间导致MLE)
利用前缀和思想,用n颗主席树分别维护1~i区间内的信息,合并重复信息即可。

哦对了因为是权值线段树,所以要离散化,
既减少空间,也避免下标出现负数。

目前上面我只会上述这些解释,其实它还能应用于可持久化操作……

6.6.2 例题应用

Caioj1441
Poj2104
Hud2665

区间第k小(大)询问
先利用前缀和获得对应区间信息,然后根据左右儿子的信息值,
找到k在哪里,不断缩小范围,最后找到他的值。

caioj和hdu都AC
然鹅,poj却RE,至今迷离,放弃治疗……

6.6.3 例题代码

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
//Zory-2018
//*******************头文件*******************
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
//*******************全局常量*******************
const int MAXN=100000;
const int NUL=0;
//*******************全局定义*******************
struct nod
{
int x,p,z;
}d[MAXN+10];
//*******************离散化*******************
bool cmp(nod a,nod b)
{
return a.x<=b.x;
}
void lsh(int n)
{
sort(d+1,d+1+n,cmp);
for(int i=1;i<=n;i++) d[d[i].p].z=i;
}
//*******************主席树*******************
struct mg
{
int lc,rc;
int c;
}s[20*MAXN];
int ln;
//因为动态建树,l、r要放这里
void add(int &x,int l,int r,int c)
{
if(x==NUL)
{
x=++ln;
s[x].c=0;
s[x].lc=s[x].rc=NUL;
}
s[x].c++;
if(l==r) return;
int mid=(l+r)/2;
if(c<=mid) add(s[x].lc,l,mid,c);
else add(s[x].rc,mid+1,r,c);
}
void merg(int x,int &y)
{
if(x==NUL) return;
if(y==NUL) {y=x;return;}
s[y].c+=s[x].c;
merg(s[x].lc,s[y].lc);
merg(s[x].rc,s[y].rc);
}
//x、y是节点编号,l、r是离散化值即排名
int ask(int x,int y,int l,int r,int rk)
{
if(l==r) return d[l].x;//排名为l的原值
int xlc=s[x].lc,ylc=s[y].lc;
int ls=s[ylc].c-s[xlc].c;
int mid=(l+r)/2;
if(rk<=ls) return ask(xlc,ylc,l,mid,rk);
return ask(s[x].rc,s[y].rc,mid+1,r,rk-ls);
}
//*******************主函数*******************
int ys[MAXN+10];
int main()
{
//int t;scanf("%d",&t);
//while(t--)
//{
ln=0;memset(ys,NUL,sizeof(ys));
int n,m;scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&d[i].x),d[i].p=i;
lsh(n);
for(int i=1;i<=n;i++)
{
add(ys[i],1,n,d[i].z);//插入一条链
merg(ys[i-1],ys[i]);//合并从而形成前缀和
}
while(m--)
{
int l,r,k;scanf("%d%d%d",&l,&r,&k);
printf("%d\n",ask(ys[l-1],ys[r],1,n,k));
//注意前缀和的-1
}
//}
}

6.6.4 练习

Bzoj1901 Zju2112
Dynamic Rankings
Spoj3267 D-query

6.4.7 所有题目

Tag-主席树

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/d299.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%