囧，现在才学。而且发现，主席树和以前写过的线段树维护名次是差不多的，，，只是用多颗线段树维护区间信息，然后可以像前缀和一样的加减。
恩，慢慢来写这篇博文。（各种定义以及背景我都掠过了）
我先说主席树的构成吧（省略大堆专业术语，我只写通俗易懂的）
我们假设现在要维护的数组是a[]
一颗主席树T[i]其实就是一个线段树，维护[x, y]的区间，其中x是我们要维护的a[]当中最小的数值，y为最大的数值（和名次线段树一样的），然后维护a[1]~a[i]的数值在区间[x, y]的数量，注意，是数值的数量：比如，a[]={2, 5, 7}, 那么T[3]维护的数值就是[2, 7]中a数组数值出现的数量，即3；T[2]维护的就是[2, 7]中a[0-1]值的数量（下标从0开始），即2。恩，只要你会线段树，你应该知道各子树维护的区间是多少以及他们的值是多少了吧。
够详细了吧。。
好了，我们求出了所有的主席树。而且可以发现（我一开始没理解，其实好好想想就行了），这是可以区间加减的。比如我们要查询[l, r]的第k小，恩，我们用T[r]和T[l-1]的主席树来做，（和名次线段树差不多），将他们维护的值相减（和前缀和相减一样的思想），那么我们就能得到你要的k值的值是在左边还是右边，举个例子，我们要查询的区间是[1, 3]，k为2，
（等等再更，待会有比赛）
原文：http://www.cnblogs.com/iwtwiioi/p/3901398.html