在课堂上，我们学习了RMQ到LCA到RMQ的问题，以及如何在O（1）时间内支持操作范围最小查询作为练习，我的教授指派我支持这个操作：o（n）空间中的范围中值查询、o（n）预处理时间和o（1）选择时间。
假设我有一个数组A，它包含8、7、9、2、6、4、5、3给定中值（i，j），在对数组进行排序之后，我们应该得到第i个元素和第j个元素（包括）之间的中值。排序是2，3，4，5，6，7，8，9。例如中值（2,6）=A[4]=6（因为4，5，6，7，8的中值是6）。
我发现了其他建议使用段树的解决方案，但在这些情况下的复杂性不是O（1）。有没有可能以类似的方式解决这个问题，我们解决的RMQ到LCA到RMQ的问题？
最佳答案
这是不可能的比较如果是，您可以通过预处理输入并计算从0到n-1的每个i的中值（i，i）来比较o（n）时间内排序n个元素。
关于algorithm - 使用预处理在数组中以O(1)时间进行范围中值查询，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/51014801/