首页 > 代码库 > 主席树(函数式线段树)学习小结(附手绘讲解图片)

主席树(函数式线段树)学习小结(附手绘讲解图片)

主席树是一种离线数据结构,是由很多棵线段树组成的。


第i棵线段树存的是前i个数的信息:

每一个线段存数字的出现次数(因此建树之前要离散化)。


那么n棵线段树不会MLE吗?


当然会了!


但是我们发现第i棵线段树和第i-1棵线段树是非常相似的,有许多结点完全相同,因此可以借用之前的结点,没必要新建结点。


具体建树方法建下图:


序列为 1 3 4 2




那么如果要询问i-j之间数字出现的次数怎么办呢?


因为每一棵线段树的区间都是相同的,所以要求l-r之间的数字的出现次数只要用前r位出现的次数减去前l-1位出现的次数,就是ans



但是如果有修改操作怎么办?


如果沿用上面的做法,那么修改操作是O(nlogn)的,查询是O(1)的,修改要花好长时间。。。


前缀和联想到了树状数组,那么将前缀和用树状数组维护的话修改是O(logn*logn),查询时O(logn),查询的时间虽然变长,但是修改的时间缩短许多!!


注意:

函数式线段树的数组要开大一点!!


代码:

无修改求区间第k大:

POJ2104 见这里


有修改求区间第k大:

BZOJ1901 见这里





主席树(函数式线段树)学习小结(附手绘讲解图片)