首页 > 笔记 > 主席树学习总结

主席树学习总结

进入了寒假。。

主席树,是一种非常优美的线段树,它的思路很好理解,但是实现比较难想。

简介

为何称呼为主席树呢?因为他的发明者是 这个人

我们研究一下他的名字

hjt

不禁想起了某主席

 

主席树又叫函数式线段树或有历史版本的线段树

顾名思义,就是可以随时提取历史版本

假如有一道题要你提取历史的线段树

你的第一反应就是建n个线段树

但是线段树的空间本来就是非常蛋疼的

假如开n个,就不用活了

 

但是假如我们看一下修改前后的线段树

images

 

我们可以发现,只有一条链被修改了!

所以,对于每一次修改,只需要建一条logn 的链就行了。

如图所示

images

 

这样,只需要记录下每次的根节点就可以愉快的实现了

题目

一道裸题

poj2104

大意:给定数列于区间,求区间第k大的数

简化版本

假如就给你n个数,让你求第k大怎么求

 

首先排序,离散化一下(离线

让后用离散后的数建立一颗线段树

但是这颗线段树不行以权值为节点储存的

它的每个节点存储的就是当前下标数字在范围内出现的次数

例如离散后为

4 2 1 3 2

那么我们建出的线段树为

images

 

假如我们查询第k大的话

那么从根开始

假如他的右孩子的权值大于等于k的话

走到右儿子

假如小于的话

走到左儿子,并k等于这个权值减k

假如我们要查询第4大的数images那么假如我们要求区间i,j的k大的话,就可以在区间i-1,j分别构建两棵优美的线段树然后差分,查出第k大的即可。

images

 

那这样的话,我们就可以对于每一个数列中的点建立一颗线段树,就可以求区间了

 

于是就变成了一道主席树的裸题

对于每一个点插入总线段树,都建一条链,存一个点,就能随时提取区间了

 

这里再讲一些关于实现的细节。

我们普通实现的线段树是一个静态的内存池,我们可以用根的下标算出左右儿子的下标。

但是对于主席树就不行了,因为它是不断改变的。这样我们就想出了一个新的思路:“动态开点的线段树”

我们对于每个节点记下它的左右儿子的下标,就ok了。

我们可以具体看一下动态开点的代码。

我们该怎么理解呢?

我们原先带进去的那个\(now\),其实是原来的节点,\(num\)是我们要把它改变成哪个数。

我们一开始的语句

就是把它变成原来的节点,这样的话我们只要修改需要修改的左儿子或者右儿子就可以了。其实就是加新链的过程。

而这一句我们就改变了now的值,别忘了上面的now带的是地址,这样上一层就直接修改了。

明白这些就可以开始码了。

代码

再来看道例题

luogu3168

题目描述

最近实验室正在为其管理的超级计算机编制一套任务管理系统,而你被安排完成其中的查询部分。超级计算机中的任务用三元组(Si,Ei,Pi)描述,(Si,Ei,Pi)表示任务从第Si秒开始,在第Ei秒后结束(第Si秒和Ei秒任务也在运行),其优先级为Pi。同一时间可能有多个任务同时执行,它们的优先级可能相同,也可能不同。调度系统会经常向查询系统询问,第Xi秒正在运行的任务中,优先级最小的Ki个任务(即将任务按照优先级从小到大排序后取前Ki个)的优先级之和是多少。特别的,如果Ki大于第Xi秒正在运行的任务总数,则直接回答第Xi秒正在运行的任务优先级之和。上述所有参数均为整数,时间的范围在1到n之间(包含1和n)。

输入输出格式

输入格式:

输入文件第一行包含两个空格分开的正整数m和n,分别表示任务总数和时间范围。接下来m行,每行包含三个空格分开的正整数Si、Ei和Pi(Si<=Ei),描述一个任务。接下来n行,每行包含四个空格分开的整数Xi、Ai、Bi和Ci,描述一次查询。查询的参数Ki需要由公式 Ki=1+(Ai*Pre+Bi) mod Ci计算得到。其中Pre表示上一次查询的结果,对于第一次查询,Pre=1。

输出格式:

输出共n行,每行一个整数,表示查询结果。

输入输出样例

输入样例#1:
输出样例#1:

说明

样例解释

K1 = (1*1+3)%2+1 = 1

K2 = (1*2+3)%4+1 = 2

K3 = (2*8+4)%3+1 = 3

对于100%的数据,1<=m,n,Si,Ei,Ci<=100000,0<=Ai,Bi<=100000,1<=Pi<=10000000,Xi为1到n的一个排列

 

我们可以这样考虑,首先把所有的点读进来,然后按照时间排序,建主席树的时候按照时间轴建权值线段树,这样就保证了每次查询的时候当前时间点前的都加了,后的都没加。。

实现比较简单

 

 

进阶

假如要在数列中更改节点的数值改怎么办呢

例题

bzoj1901

(权限题,交不了就用 zoj2112 但是zoj的内存限制非常蛋疼

题目

Description

给定一个含有n个数的序列a[1],a[2],a[3]……a[n],程序必须回答这样的询问:对于给定的i,j,k,在a[i],a[i+1],a[i+2]……a[j]中第k小的数是多少(1≤k≤j-i+1),并且,你可以改变一些a[i]的值,改变后,程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序,从输入文件中读入序列a,然后读入一系列的指令,包括询问指令和修改指令。对于每一个询问指令,你必须输出正确的回答。 第一行有两个正整数n(1≤n≤10000),m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有n个数,表示a[1],a[2]……a[n],这些数都小于10^9。接下来的m行描述每条指令,每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k (i,j,k是数字,1≤i≤j≤n, 1≤k≤j-i+1)表示询问指令,询问a[i],a[i+1]……a[j]中第k小的数。C i t (1≤i≤n,0≤t≤10^9)表示把a[i]改变成为t。

Input

对于每一次询问,你都需要输出他的答案,每一个输出占单独的一行。

Output

Sample Input

5 3

3 2 1 4 7

Q 1 4 3

C 2 6

Q 2 5 3

Sample Output

3

6

HINT

20%的数据中,m,n≤100; 40%的数据中,m,n≤1000; 100%的数据中,m,n≤10000。

大意就是可以随时改变区间中数的值,询问区间的第k大的值

现在我们若是按着上面的思路:仍然是做桶,仍然是利用前缀和相减。但是对某个元素的修改,会影响到其后面所有的前缀和,于是对后面的也都进行一次修改。[可这每个操作都是nlogn的…明显太慢]

于是我们想起了一种可以快速修改和获得前缀和的数据结构——树状数组。

每次修改时只需要修改[j+lowbit(j)]等等的元素,每次二分下去时需要对x,y两棵子树分别求前缀和[j-lowbit(j)]等等的和。

这样修改和获取前缀和的复杂度都是logn的,所以每次操作都是(logn)^2的。

再分析一下空间复杂度:

回顾之前,我们虽然建了n棵树但事实上很多部分是相同的,所以那些部分我们都没有管,只是将节点与上一个节点定为相同,然后对于变化的部分再操作。

那么我们这道题如果按照上面的方法大概是不太可行的,因为现在我们每棵线段树表示的是树状数组中的含义[例如6表示5+6,12表示9+10+11+12等等…]

也就是说每次修改的前一个是可能不同的,不能将当前节点设为原来的节点改[事实上,原来那种改法是因为前驱只有一个以及只要修改一个设计出来的,而我们这里两个都不满足],但是有一点思想是好的,就是我改变的每次都只有一条链,而每次修改就是添加一条链上去,不是整个线段树已经建好了再去修改[有点类似Trie树的构造],所以空间上复杂度也不吃紧,(n+m)(logn)也是可以接受的。

上面主要讲了使用什么样的线段树,下面具体说一下怎么使用线段树的问题。

操作0:因为线段树在这里做桶,于是使用Hash来离散化,即预处理快排一下,然后查找的时候二分找对应的位置。[注意:因为操作中有修改元素的操作,所以离散化需要将这些元素也包含在内,这就需要离线处理]

操作1:预处理原序列:对于第i个元素,对i及i后面的[指树状数组中i+lowbit(i)的]所有节点都加上这个元素。

操作2:修改某个位置上的元素的值:首先按原来的值在这个节点及以后的所有节点上-1,然后按新的值在这个节点及以后的所有节点上+1

操作3:询问一段区间内排行第k的元素:和静态类似。但是每次求左右子树的前缀和时使用树状数组

代码:

 

images

 


2 COMMENTS

  1. wsmrxc2018-02-25 上午9:33

    写的很棒啊!

如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×