所谓主席树呢，就是对原来的数列[1..n]的每一个前缀[1..i]（1≤i≤n）建立一棵线段树，线段树的每一个节点存某个前缀[1..i]中属于区间[L..R]的数一共有多少个（比如根节点是[1..n]，一共i个数，sum[root] = i；根节点的左儿子是[1..(L+R)/2]，若不大于(L+R)/2的数有x个，那么sum[root.left] = x）。若要查找[i..j]中第k大数时，设某结点x，那么x.sum[j] - x.sum[i - 1]就是[i..j]中在结点x内的数字总数。而对每一个前缀都建一棵树，会MLE，观察到每个[1..i]和[1..i-1]只有一条路是不一样的，那么其他的结点只要用回前一棵树的结点即可，时空复杂度为O(nlogn)。
转自：https://blog.csdn.net/creatorx/article/details/75446472
主席树的作用、其能够查询不修改的区间K大值、区间不同数的个数、套个树状数组还能查询动态K大值......
这几天看感觉不是很懂，推荐几个博客：链接1（附加题目）、链接2、链接3
下面是hdu2665 Kth number 的代码：
hdu2665