JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Tutorial Discussions Range Minimum Query and Lowest Common Ancestor Re: Good job. Revision History (2 edits)
Re: Good job. (response to post by hungson175)
You have to normalize the array first, as described in the article. After that, you may use the algorithm described at the end of the article.
[LATER EDIT]
Note that you don't actually normalize A, this is a forced expresion. You just use LCA queries for computing the RMQ queries on the original vector. For that LCA queries you use RMQ queries on a +-1 vector, and that's the vector you process. So, the way that's described in the article, it's necesarry to build the cartesian tree first, and compute the euler tour on it in order to have an <O(n), O(1)> RMQ algorithm.
However, don't expect to code this algorithm in a topcoder contest;). It's just too long to code:)
Re: Good job. (response to post by hungson175)
You have to normalize the array first, as described in the article. After that, you may use the algorithm described at the end of the article.
[LATER EDIT]
Note that you don't actually normalize A, this is a forced expresion. You just use LCA queries for computing the RMQ queries on the original vector. For that LCA queries you use RMQ queries on a +-1 vector, and that's the vector you process. So, the way that's described in the article, it's necesarry to build the cartesian tree first, and compute the euler tour on it in order to have an <O(n), O(1)> RMQ algorithm.
However, don't expect to code this algorithm in a topcoder contest;). It's just takes too long to code:)
Re: Good job. (response to post by hungson175)
You have to normalize the array first, as described in the article. After that, you may use the algorithm described at the end of the article.