c++ - 算法 - 关于序列中位数的许多查询

Question

我们有一个序列 a₁, a₂, ..., a_n 其中 a_i是整数， |a_i| <= 10⁶ 且 n <= 10⁶。我们有 m 个查询，其形式为:“i j”，意思是“序列 a_i, a_i+1, ..., a _{序列中的中位数是多少j}？”

你知道该怎么做吗？我知道有一种算法可以在线性时间内按顺序查找中位数( https://en.wikipedia.org/wiki/Median_of_medians )，但将其应用到每个查询中太慢了。

Answer 1

该问题称为范围中值查询。有些算法具有不同的复杂性和属性，请参阅 this和 this作为起点。

来自 Mark Gordon 在 Quora 上的回答:

Create a two dimensional orthogonal range tree created from the N points of the form (A[i], i). Constructing this tree can be done easily in O(N log^2 N) time (although O(N log N) is possible).

Now to query the kth element we traverse the first dimension of the tree. We follow the left subtree if the number of points within our query index range in the left subtree is smaller than k. This is simply a query on the second dimension tree of the left subtree. If the kth element isn't in the left subtree we adjust k appropriately and search in the right subtree. This whole search takes O(N log^2 N) time. Essentially we have dropped a log N factor from Johnny's solution by wrapping the binary search into the traversal of the tree.

It's actually possible to get this down to O(N log N) preprocessing and O(log N) per query. Skip to about 17:00 in 6.851: Advanced Data Structures (Spring'12) to see Erik Demaine explain orthogonal range trees and how to achieve the faster preprocessing and query times which take mild cleverness and fractional cascading respectively.

如果您搜索问题名称，还有一些专门针对该主题的研究论文。这不是一个简单的问题，您可能需要阅读一些文档才能掌握解决方案。我首先观看我引用的 Quora 答案中链接的视频。

不幸的是，我对这个主题的理解还不够深入，无法以这种格式很好地解释它。如果有人这样做，请随时编辑此答案或发布您自己的答案，我将删除我的答案。