伪距最小查询 [英] Pseudo Range Minimum Query

问题描述

我的作业存在问题，需要我解决与range-minimum-query类似的问题.该问题大致描述如下:

I have a problem with my assignment which requires me to solve a problem that is similar to range-minimum-query. The problem is roughly described below:

我应该编写一个Java程序，该程序读取一大堆整数(大约100,000)并将它们存储到某种数据结构中.然后，我的程序必须回答给定范围[i，j]中的最小数量的查询.我已经成功设计出一种算法来解决这个问题.但是，这还不够快.

I am supposed to code a java program which reads in large bunch of integers (about 100,000) and store them into some data structure. Then, my program must answer queries for the minimum number in a given range [i,j]. I have successfully devised an algorithm to solve this problem. However, it is just not fast enough.

我算法的伪代码如下:

// Read all the integers into an ArrayList

// For each query,
// Read in range values [i,j] (note that i and j is "actual index" + 1 in this case)
// Push element at index i-1 into a Stack
// Loop from index i to j-1 in the ArrayList (tracking the current index with variable k)
[Begin loop]       
// If element at k is lesser than the one at the top of the stack, push the element at k into the Stack.
[End of loop]

有人可以建议我该怎么做，这样我的算法才能足够快地解决此问题?

Could someone please advise me on what I could do so that my algorithm would be fast enough to solve this problem?

可以在以下链接找到分配文件: http://bit.ly/1bTfFKa

The assignment files can be found at this link: http://bit.ly/1bTfFKa

这个问题困扰了我好几天了.任何帮助将非常感激. 谢谢.

I have been stumped by this problem for days. Any help would be much appreciated. Thanks.

推荐答案

您的问题是静态范围最小查询(RMQ).假设您有N个数字.您可以使用的最简单的算法是创建一个大小为N的数组并存储数字的算法，另一种大小为sqrtN的算法将在数组中保存每个大小为sqrtN的间隔的RMQ.由于N不是很大，所以应该可以使用，但是如果您有很多查询，则可能要使用其他算法.
话虽这么说，您可以使用的最快算法是根据数字创建稀疏表，这将使您能够回答O(1)中的查询.构造稀疏表是O(NlogN)，在给定N = 10 ^ 5的情况下就可以了.
最后，RMQ的最终算法是使用分段树，该分段树还支持更新(单元素和范围)，构造分段树为O(N)，每次查询和更新为O(logN). 所有这些算法都可以很好地公开此处. 有关段树"的更多信息，请参阅我自己编写的这些教程.

Your problem is a static range minimum query (RMQ). Suppose you have N numbers. The simplest algorithm you could use is an algorithm that would create an array of size N and store the numbers, and another one that will be of size sqrtN, and will hold the RMQ of each interval of size sqrtN in the array. This should work since N is not very large, but if you have many queries you may want to use a different algorithm.
That being said, the fastest algorithm you could use is making a Sparse Table out of the numbers, which will allow you to answer the queries in O(1). Constructing the sparse table is O(NlogN) which, given N = 10^5 should be just fine.
Finally, the ultimate RMQ algorithm is using a Segment Tree, which also supports updates (single-element as well as ranges), and it's O(N) to construct the Segment Tree, and O(logN) per query and update. All of these algorithms are very well exposed here. For more information in Segment Trees see these tutorials I wrote myself. link
Good Luck!

这篇关于伪距最小查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！