首页 > 代码库 > 主席树(函数式线段树)学习小结(附手绘讲解图片)
主席树(函数式线段树)学习小结(附手绘讲解图片)
主席树是一种离线数据结构,是由很多棵线段树组成的。
第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 见这里
主席树(函数式线段树)学习小结(附手绘讲解图片)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。