我这几天稍微看了一下区间第 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)。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 129.170.195.149 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1423156670.A.4C6.html ※ 编辑: FRAXIS (129.170.195.149), 02/06/2015 05:22:15