CODEWITHSUNDEEP
java
elahe
elahe

Reputation: 49

What data structure using O(n log n) storage with O(log n) query time should I use for Range Minimum Queries?

Suppose that we are given a sequence of n values x1, x2 ... xn, and seek to quickly answer repeated queries of the form: given i and j, find the smallest value in xi... xj Design a data structure that uses O(n log n) space and answers queries in O(log n) time.

I know the solution of data structure with O(n) space and O(log n) time , but I need an answer that uses O( n log n) space not less .

any suggestions ?

solution for O(n) space :

O(n) space : For input of a1,a2,a3,...an , construct a node that contains minimum of (a1,..,ak) and minimum of (ak+1,..,an) where k = n/2. Recursively construct the rest of the tree. Now, if you want to find the minimum between ai and aj: Identify the lowest common ancestor of i,j. Let it be k Start with i and keep moving until you hit k. AT every iteration check if the child node was left node. If yes, then compare the right subtree's min and update current min accordingly. Similarly, for j, check if it is right node.... At node k compare values returned by each subtree and return the min

Upvotes: 3

Views: 998

Answers (1)

NPE
NPE

Reputation: 500247

First of all, O(n) is also O(n logn), so technically any solution that's O(n) is automatically also O(n logn).

What you seem to be asking is a solution that uses Θ(n logn) memory (note the theta). I have to say I think this is a slightly odd requirement given that you claim you already have a superior Θ(n) solution.

In any case, you can trivially transform your Θ(n) solution into a Θ(n logn) one by making log(n) copies of your data structure.

Upvotes: 3

Related Questions