主席树详解

主席树——BY徐亦轲HDU2665•给定n个数字，m个询问，每次求[L,R]内的第k大值•N=100000•询问次数=100000•线段树？然而只能查最大主席树【可持久化线段树/函数式线段树】（PERSISTENTTREE）•一种神奇的数据结构•一种离线数据结构•可以查询区间第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代码略长不贴了想看的的同学们：unique可以快速去重lower_bound可以快速找到原数在离散化后的排名【STL大法好】如果要动态求区间第K大（即支持修改操作）？1=N=50,000，1=T=10,000主席树是用前缀和来维护的查询为O(1)，但修改为O(n)如果不用前缀和，则查询为O(n)，修改为O(1)有没有折中的办法？还记得之前学的树状数组吗？不正好可以用在这个地方？BZOJ1901/ZOJ2112DYNAMICRANKINGS•给你n个数，m次操作，每次修改一个数或者求一段区间内的第k大值。（n=50000，m=10000）BZOJ1901/ZOJ2112DYNAMICRANKINGS•首先读入所有数和全部操作，将会出现的数离散化，以树状数组结构建立主席树；修改和查找和普通主席树相似，只不过使用了树状数组。BZOJ1901/ZOJ2112DYNAMICRANKINGS代码链接：【bzoj1901】dynamic-rankings/是不是特别简单？•THEEND