我这几天稍微看了一下区间第 k 大，不知道自己想的对不对，
上来跟大家讨论一下。 （不好意思这篇很长）
题目是这样： 给定 n 个整数的阵列 A，以及 m 个查询 [lj, rj], kj
找出 A[lj..rj] 的第 k 大数字
http://ppt.cc/24oD 这边是 wiki 的介绍
以下是一些可行的方法，机器模型是 RAM 而且每个元素只使用 O(1) 空间，
假设 A[i] 的范围是 [1..m]。
1. 类似 wiki 上面的方法（划分树）
建立一个树的结构，每个节点代表着 [1..m] 的一个区间，
节点里面纪录一个阵列 B ，B[i] 代表 A[1..i]的元素中比 m / 2 小的个数。
树根代表整个阵列，左子树代表所有小于m/2的元素，右子树代表剩下的元素，
可以递回建立起整棵树。空间复杂度是O(n lg n)，查询可以做到O(lg n)。
2. 几何方法
给定一个查询[lj, rj], kj时，我们可以用二分搜寻的方法来找出一个在[lj, rj]
中的元素，使得该元素在[lj, rj]中的 rank 为 kj。
对于任何元素 x ，如果我们可以在O(lg^2 n)的时间内计算
出 x 在 [lj, rj] 中的 rank，那只要binary search on x ，我们就可以得到
在O(lg^3 n)的时间内找出[lj, rj]中第 kj大的数字。
把输入想像成平面上的 n 个点 (i, A[i])，找出 x 在 [lj, rj]中的 rank
其实等价于找出 lj <= i <= rj 且 A[i] >= x 的点个数。
就变成3-side range query了，用 range tree 或是 priority search tree，
都可以在O(lg^2 n)作 counting query。
priority search tree有点类似归并树。
如果可以使用fractional cascading或是generalized selection，
那区间 k 大的查询可以在O(lg^2 n)的时间完成。
3. Fully persistent data structure
另外一种同样基于二分搜寻的想法，当要搜寻 x 在[lj, rj]的rank时，
因为rank(lj, rj, x) = rank(1, rj, x) - rank(1, lj-1, x)，
所以如果有一种资料结构，可以在O(lg n)的时间内作rank(1, j, x)的查询，
那我们就可以在O(lg^2 n)的时间内找出[lj, rj]中第 kj 大的数字。
如果是计算rank(1, n, x)，那么我们可以只要建立一个二元搜寻树就好了。
但是因为是要 query rank(1, j, x)，我们需要一个资料结构，可以回朔到
第 j 次插入之后的状态，同时间还可以查询。
而fully persistent data structure就满足要求。
这边有另外一个几何解释，我们可以把第 i 个元素看成是一条从(i, A[i])
开始，往右平行 x 轴的射线。
rank(1, j, x)实际上就是计算从(j, x)往上平行 y 轴的射线与多少平行
x 轴的射线相交。
就变成window query，用 segment tree 可以在O(lg n)计算出来。
4. 主席树
其实就是设计一个特殊的资料结构来加速二分搜寻。
在方法 2 和 3 中，rank的计算方法是很一般性的，但是在这个问题上，
其实不需要那么一般性的 rank 计算法，因为会查询的 x 是基于二分搜寻的。
所以要设计一个特殊的资料结构来加速。
借由 3 的几何解释，我们知道rank(1, j, x)是对于 x 递增的。
所以对于每一个 j ，可以使用一个 Fenwick tree 来维护rank(1, j, .)。
我们又知道rank(1, j, .)和rank(1, j+1, .)差别不大，所以可以使用
persistent data structure来建构这 n 个树（这边我们不需要fully的性质）。
计算rank(lj, rj, x)时，实际上是同时top-down traverse
两颗Fenwick tree: rank(1, lj, .) 和 rank(1, rj, .)
查询的时间复杂度是O(lg n)。
区间 k 大 加上修改
方法 1 我是不知道能不能变成动态。
方法 2 是动态的 3-side range query，查询应该是可以做到O(lg^2 n)。
方法 3 的话就要改使用 retroactive data structures，不但可以查询
第 j 次插入后的结果，还可以修改第 j 次的操作，结果反应到所有 > j的结构。
应该也是可以O(lg^2 n)。
方法 4 我看了很多文章还是不懂怎么变成动态。
但是我自己想了一个动态的方法，不知道对不对。
当计算rank(1, j, x)时，利用方法 2 的几何解释，实际上是在计算
满足 1 <= i <= j 且 A[i] >= x 的点数。
所以我们只要设计一个动态的资料结构支援2-side range query，
同时又可以对于二分搜寻加速即可。
因为rank(1, j, x)是对于 j 递增的，所以理论上
对于 每一个 x 都维护一个 binary search tree ， 储存所有的 i 满足
A[i] <= x。但是这样修改的操作会太慢。
所以在外层要使用一个 静态树 的结构，类似方法 1。
每个节点表示 [1..m] 的一个区间，储存一个 binary search tree，其中元素
是所有的 i 满足 A[i] 在这个区间的。
然后左子树表示所有小于m/2的区间，右子树表示剩下的区间。
二分搜寻的每一个查询都可以在O(lg n)内完成，所以查询复杂度为O(lg^2 n)。
修改的话只是把 binary search tree 的元素加入和删除，复杂度也可为O(lg^2 n)。