可持久化线段树学习笔记

起因是16长春CCPC遇到了一个全场万人过的主席树题目,然而我不会orz,哭哭

可持久化线段树的本质是很多棵形态完全相同的线段树。

也可以理解成是,保存了不同时刻版本的线段树的数据结构。

如果没有可持久化线段树,那么我们如果需要不同时刻的线段树,无脑的做法可能是,需要多少个时刻的线段树,就建多少棵线段树。

但是空间绝对gg,我们考虑每次修改,其实对于一次修改,线段树上只有很少一部分被修改了,其他部分都一样。

因此,我们很容易想到,我们何不只考虑修改的部分,其他部分共用,以减少时间和空间消耗呢?

  • 可持久化线段树是利用函数式编程的思想,对记录的数据只赋值不修改,每次插入一个数据后保存一个历史版本,然后利用线段树的结构完全相同,可以直接相减的特性进行区间询问。

 

可持久化线段树有几个经典应用,比如求区间第k大  静态区间第k大   动态区间第k大 

静态区间第k大的思想:

  • 首先,给你一颗值为横坐标的线段树,每个节点上存着该值出现了多少次,这样的一颗线段树你会求区间k大值吧.二分即可.
  • 然后,假设区间是数组arr[n],区间长度是n,那么给你n颗线段树,第i颗线段树是第i-1颗线段树插入arr[i]得到.
  • 如果你有了这n颗线段树,想求区间[l,r]中的第k大值,那么你需要在第r颗和第l-1颗线段树的差线段树上作二分,就可以求得区间第k大值.
  • 差线段树很好理解,比如你有一个部分和数组sum,sum[r]-sum[l-1]就是部分和的差,代表区间[l,r]的和,差线段树同理.
  • 现在,可持久化线段树出现为你解决最后一个问题,空间问题.内存很小,不能够存下n颗线段树,但是,第2条中提到,由于第i颗线段是是第i-1颗线段是插入仅一个值得到的,两颗线段树的区别不大,仅有log(n)个节点发生了改变,我们仅仅需要记录这log(n)的数据就可以记录这个增量,这就是可持久化线段树.

以及求区间中不同数的个数   spoj-dquery 求区间中不同数的个数

思想其实和离线线段树是一样的。

在学习可持久化线段树的时候,遇到过一个叫”权值线段树“的概念

其实并不是什么新东西,只不过是把值作为节点来考虑,参考逆序对的线段树|树状数组 求法…(由于是在值域上建立线段树,所以常常需要离散化)

这思想不是很常见么….感觉完全没必要安个名字…以及,怎么不给BIT也起个叫权值BIT啊orz

 

 

参考资料:

知乎-主席树是如何求区间k大的?

可持久化数据结构之主席树

 

 

2016 CCPC 长春 I 题 | hdu 5919 Sequence II (可持久化线段树求区间第k大+可持久化线段树求区间不同数个数)

题目链接

题意:

给定一个序列 n,有 m次查询,每次查询一个区间[l,r],求区间中每一种数在区间中第一次出现的位置的中位数,强制在线。

思路:

先分解一下问题,我们要求一段区间位置的中位数,其实可以分解成,求区间中不同数的个数+求区间中第k大的下标。

对于求区间中不同数的个数,离线可以随便线段树,树状数组,或者莫队也行(观察到数据范围<=2E5)

在线的话,就只能可持久化线段树了。

看到一些题解中说要倒序处理…但是之前写求区间不同数的个数,我都是倒序处理的啊? (回想一下,当时似乎正序处理也行…

倒序处理是为了,处理到第i个的时候,第i个一定是当前后缀区间中,第一个出现的…

然后第二个问题,求区间中第k大的下标,离线做法不少,在线的话,也可以用可持久化线段树求。

所以感觉就是板子题,可持久化线段树的2个应用放在了一起orz

 

 

 

bzoj 1901: Zju2112 Dynamic Rankings (可持久化线段树,区间动态第k大)

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继续回答上面的问题。

Input

第一行有两个正整数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
m,n≤10000

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

思路:

现在我们已经会了用可持久化线段树,去做静态区间第k大的问题。

考虑一次修改,修改的元素会影响后面所有建好的线段树,时间代价是无法承受的。

我们考虑root[i]表示的这颗线段树,它保存的是从第一个元素开始插入到第i个元素后的数字区间。也就是说每次我们进行线段树区间相减时,我们是对两个前缀和[1, l – 1]和[1, r]进行了相减。

所以我们需要的是,以一个可以接受的时间代价,维护一个前缀和。

显然是用BIT来维护。

所以带修改的可持久化线段树,本质上应该是BIT套可持久化线段树。

 

 

 

hdu 2665 Kth number (静态区间第k大,可持久化线段树模板题)

题意:

求区间第k大数

思路:

可持久化线段树。

其实这东西在国内更常见的名字应该是 zhu xi 树?应该是由于“中国高端数据结构领导者”的hjt比较早得引入(?推广?)而得来的。

不过之前没写什么东西都被封,写个zhu xi 树,怕是政治敏感够枪毙100回了orz

似乎也叫函数式线段树。

写个模板题练下手。学习笔记之后补。

 

 

 

spoj DQUERY – D-query (询问区间中不同数的个数,线段树(离线) or 莫队算法(离线) or 主席树(在线))

题目链接
题意:给出n个数,然后m个询问,每个询问一个区间[l,r],问该区间中不同的数有多少个。

思路:离线处理+线段树的做法不多说了:

之后补一个主席树的做法

先来补一个莫队的做法。

因为a[i]<=1E6,可以很方便得统计每个数出现的次数,update的时候,如果是1变成0,那么区间中不同的数的个数减1,如果是0变成1,那么区间中不同数个数+1

 

补一个在线的做法,可持久化线段树,其实思路和离线线段树几乎一样。