RT
一直以为主席树就是划分树的说…… 前两天才发现完全不是一回事……TAT
主席树可能更接近函数式线段树一些，用途貌似主要是解决一些区间询问问题。
比如说区间K大…… 先考虑没有修改的，那么先离散掉，然后对于每个前缀区间[1,i]都建一颗线段树，表示区间[1,i]里每个元素出现了多少次，然后发现tree[i]修改lgn个节点就得到tree[i+1]，于是可以用函数式线段树……这样就O(nlgn)了
然后发现主席树有很好的性质就是对应节点可以直接相减，tree[r]-tree[l]就得到区间[l+1,r]的情况了。于是查询区间K大直接就变成了在线段树上找X大，于是就每次O(lgn)了，和划分树复杂度一样，而且比划分树好想的多……
然后说有修改的…… 其实就是修改一个元素查询区间和？ 前缀和不行了于是就树状数组吧…… 在主席树外面套一个树状数组就行了。查询就是O(lg^2n)了，比直接二分加线段树套平衡树的O(lg^3n)要好。
还可以搞一些类似求某个数在某个区间内的出现次数之类的操作，都是比较显然的……
代码不是很难写…… 只要能理解函数式线段树的原理就行了…… 不过貌似主席树缺陷是耗内存非常严重（本来就是空间换时间的东西嘛……） 比如带修改的区间K大建树就要O(Nlg^2N)内存，在ZOJ上各种被卡内存…… 不过BZOJ上规模小一些，是能过的……
UPD: lhm_m跟我说了一种在常数上减小内存消耗的方法：插入值时候先不要一次新建到底，能留住就留住，等到需要访问子节点时候再建下去。这样理论内存复杂度依然是O(Nlg^2N)，但因为实际上很多结点在查询时候根本没用到，所以内存能少用一些。用这种方法能在ZOJ上不MLE。
POJ2104 kth number: http://ideone.com/1y5OT
BZOJ1901 Dynamic Ranking:http://ideone.com/lF7Hd