主席树(可持久化线段树单点) (函数式线段树)学习笔记

在学习主席树之前,我们先来明确几个基础的概念。

权值线段树

给出一个序列1 2 1 4 5 2 3 1

正常的线段是(如维护区间和)

19

8      11

3   5   7   4

1 2 1 4 5 2 3 1

然而权值线段树是对于数据范围,记录每一个数字出现的次数,对于这个出现的次数构造一颗线段树

这样子原序列就变成了

1 2 3 4 5 (范围)

3 2 1 1 1 (对应元素个数)

然后建成一颗线段树,这就是权值线段树。

可持久化线段树。

可以查询历史版本的线段树,如果暴力的搞,那么我们需要建许n(版本数量)棵线段树。复杂度为n * m (m为元素个数),显然这是有MLE的风险的。我们考虑如果我们修改一个单点,那么对于一颗新版本的线段树,显然只有从叶节点到根节点的一条链上有所改变,其余部分没有改变。那么我们可以考虑对于改变的部分重新建一颗树,对于相同的部分,就直接连到之前版本的那个部分。这样子我们就可以在一个比较优美的多余的一个log复杂度完成可持久化。

现在我们来考虑一下主席树

主席树是一颗可持久化的权值线段树,可以快速进行查询区间第K大等操作。因为主席树基于权值线段树,所以是一种离线的数据结构,需要提前知道数据的范围来进行构造,并且极有可能需要离散化。

下面我们从查询区间第K大来考虑一下主席树。

其中每一个版本i记录了[1,i]这个区间的权值线段树。相当于维护了一个前缀和。

那么y版本-x-1版本得到的线段树就是[x,y]区间的权值线段树。

题可以到poj2104去体验一下。

发表评论