这是一个问题，一个未排序的数组a[n]，我需要找到kth在范围[i, j]和绝对1<=i<=j<=n, k<=j-i+1中最小的数字。
通常，我将使用quick-find来完成这项工作，但是如果有很多查询请求具有不同范围的[i, j]，它的速度还不够快，我很难找出一种算法在O(logn)的时间内进行查询(允许预处理)。
任何想法表示赞赏。
PS
让我使问题更容易理解。允许进行任何类型的预处理，但是查询需要在O(logn)时间内完成。并且将有许多(超过1个)查询，例如find 1st in range [3,7], or 3rd in range [10,17], or 11th in range [33, 52]。
通过范围[i，j] ，我的意思是在原始数组中而不是排序或其他内容。
例如，a[5] = {3,1,7,5,9}，查询1st in range [3,4]是5，2nd in range [1,3]是5，3rd in range [0,2]是7。
最佳答案
当前解是O((logn)^ 2)。我很确定可以将其修改为在O(logn)上运行。与paxdiablo算法相比，此算法的主要优势是空间效率。该算法需要O(nlogn)空间，而不是O(n ^ 2)空间。
首先，从长度为m和n的两个排序数组中找到第k个最小元素的复杂度为O(logm + logn)。从长度为a，b，c，d ..的数组中查找第k个最小元素的复杂度为O(loga + logb + ...)。
现在，对整个数组进行排序并存储。对数组的前半部分和后半部分进行排序并存储，依此类推。您将拥有1个长度为n的排序数组，2个长度为n/2的数组，4个长度为n/4的排序数组，依此类推。所需的总内存= 1 * n + 2 * n/2 + 4 * n/4 + 8 * n/8 ... = nlogn。
一旦有了i和j，就可以找出子数组的列表，这些子数组在串联时会给您范围[i，j]。将要登录的数组数。在其中找到第k个最小的数字将花费O((logn)^ 2)时间。
最后一段的示例:
假设数组的大小为8(索引从0到7)。您具有以下排序列表:
A:0-7，B:0-3，C:4-7，D:0-1，E:2-3，F:4-5，G:6-7。
现在用指向这些数组的指针构造一棵树，以便每个节点都包含其直接组成部分。 A将是根，B和C是其子代，依此类推。
现在实现一个返回数组列表的递归函数。
def getArrays(node, i, j):
if i==node.min and j==node.max:
return [node];
if i<=node.left.max:
if j<=node.left.max:
return [getArrays(node.left, i, j)]; # (i,j) is located within left node
else:
return [ getArrays(node.left, i, node.left.max), getArrays(node.right, node.right.min, j) ]; # (i,j) is spread over left and right node
else:
return [getArrays(node.right, i, j)]; # (i,j) is located within right node
关于algorithm - 在O(logn)时间中找到第k个最小的数字，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/15237327/