可持久化线段树学习笔记

起因是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大的?

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

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz