arrays - 获取使用O(klogk)中的稀疏表排序的范围内的k个最小元素

Question

Sparse Table是一种数据结构，允许您在O（1）查询时间和O（nlogn）准备时间和空间（可以改进为O（n）但常数更大）中回答RMQ问题。
这意味着对于给定的静态数组（元素不变），我们可以在恒定时间内找到任意两个索引之间的最小元素。
问题是：
给定一个数组的稀疏表，我们希望添加另一个查询，以获取排序范围（升序）中的k个最小元素。

Query input  : k, left index, right index
Query output : k smallest elements in range sorted

不使用稀疏表的解决方案：
我们可以用[AA>排序得到K个最小元素，但时间复杂度是O（L+KLogk），其中L是范围的长度（k<＝L<＝n）。
但是如何使用稀疏表来减少查询到O（KLogk）的时间复杂度，而不是O（L+KLogk）？

Answer 1

这个想法与如何从O（klogk）排序的aCartesian Tree中获取k最小元素非常相似。
解决方法是使用minBinary Heap并插入树的根，然后k次从堆中移除min元素并将其子元素插入树中。
笛卡尔树问题的伪代码：

minValues(k, root):
  arr  = Array[0 . . . k - 1]
  heap = emptyMinHeap()

  heap.insert(root)
  for(i = 0 . . . k - 1):
      node <- heap.pop()
      arr[i] <- node.key

      if node has left son:  heap.insert(node.left)
      if node has right son: heap.insert(node.right)

  return arr

之所以这样做是因为笛卡尔树中节点的子节点不小于节点本身。所以我们知道最小的节点在根上，所以这是k最小的节点中的第一个。
现在，根据类似的参数，下一个最小的元素必须是该节点的两个子元素之一。
下一个最小的可能是根的另一个子节点，或者是我们刚刚获取的节点的两个子节点中的一个子节点，依此类推……
我们怎么能用这个来解决我们的问题？
我们可以将数组中的任何特定范围“视为”笛卡尔树，方法是：范围中的最小值是根（我们可以使用稀疏表在o（1）中找到它），它的左子项是根和最左索引（除非最小值在最左索引中，在这种情况下，它将为空）和右索引之间的最小值左子节点的子节点是左子节点和根节点之间的最小值，我们可以继续这样来获取每个节点的子节点，而不必实际构建笛卡尔树。
因此，我们可以对笛卡尔树使用相同的算法，但不是从笛卡尔树插入堆节点，而是插入节点的子树的范围，堆的键将是该范围的rmq（在o（1）中可以找到的范围中的最小值）。
例如：如果我们有这个笛卡尔树：

我们希望将值为3的节点插入堆，而不是插入范围：
0,2个
如果要插入值为10的节点，则插入堆：
5,9个
如果我们想插入根，我们可以插入堆：
0，10个
等等…
因为发现节点的值（范围内的最小值）取O（1），所以该算法的复杂性将是相同的（O（KLogk））。
伪代码：

//assuming our static array is called: St

K_MinValuesInRange(k, left, right, SparseTable):
  arr  = Array[0 . . . k - 1]

  /*key of node in the heap is determined
    by St[SparseTable.RMQ(node.left, node.right)]
    which takes O(1) to calculate*/
  heap = emptyMinHeap()

  heap.insert(left, right)
  for(i = 0 . . . k - 1):
      node <- heap.pop()
      min_pos <- SparseTable.RMQ(node.left, node.right)
      arr[i]  <- St[min_pos]

      /* if node has left son: insert left son*/
      if node.left < min_pos: heap.insert(node.left, min_pos - 1)

      /* if node has right son: insert right son*/
      if node.right > min_pos: heap.insert(min_pos + 1, node.right)

  return arr