主席树详解解读.pptx

主席树 ——By 徐亦轲 HDU2665 给定n个数字，m个询问，每次求[L,R]内的第k大值 N=100000 询问次数=100000 线段树？然而只能查最大 主席树【可持久化线段树/函数式线段树】（Persistent Tree） 一种神奇的数据结构 一种离线数据结构 可以查询区间第k大 复杂度log(n) 名词解释：在线/离线 在线就是一边读数据一边处理 离线就是把所有数据读完一起处理 假设只要求所有数字中第k大？ 先将所有数字离散化（排序+去重）（所以是离线） 对离散化后的数字建立一颗线段树，每个节点统计当前数字范围内的数出现了多少次 自顶向下查找，如果左边区间个数大于等于k则在左边，小于则在右边 所以复杂度log(n) 那么对于任意一段区间[L,r].. 建立n颗线段树，每棵维护[1,i]的数字出现情况 则[L,R]=[1,R]-[1,L-1](前缀和思想) 然后查找就可以了 然而还有一个问题 n棵线段树，每棵2n个点，怎么也是n2的空间 MLE? 我们有神奇的解决方法 注意到每棵新树都是上一棵树改了一条从某叶子到根节点的路径 那么除了这条路径，其他的都可以直接从上一棵树上蒯过来 大概就长这样了-- 那么空间复杂度O(nlogn) 所以HDU2665代码 略长不贴了 想看的/2015/12/%E3%80%90%E4%B8%BB%E5%B8%AD%E6%A0%91%E3%80%91hdu2665-kth-number/ C++的同学们： unique可以快速去重 lower_bound可以快速找到原数在离散化后的排名 【STL大法好】 如果要动态求区间第k大（即支持修改操作）？1 = N = 50,000，1 = T = 10,000 主席树是用前缀和来维护的 查询为O(1)，但修改为O(n) 如果不用前缀和，则查询为O(n)，修改为O(1) 有没有折中的办法？ 还记得之前学的树状数组吗？ 不正好可以用在这个地方？ Bzoj 1901/ZOJ2112 Dynamic Rankings 给你n个数，m次操作，每次修改一个数或者求一段区间内的第k大值。（n=50000，m=10000） Bzoj 1901/ZOJ2112 Dynamic Rankings 首先读入所有数和全部操作，将会出现的数离散化，以树状数组结构建立主席树；修改和查找和普通主席树相似，只不过使用了树状数组。 Bzoj 1901/ZOJ2112 Dynamic Rankings 代码链接： /2016/01/【bzoj1901】dynamic-rankings/ 是不是特别简单？ THE END