Need Help! Range Minimum Query and Cartesian Trees

Revision en2, by appro, 2016-09-04 13:09:29

I am given an array A of size n. I have to answer q queries of the form [Li,Ri]

Answer to the query [Li,Ri] is the minimum of all A[x] for all x from [Li,Ri].

1≤n,q≤10^5 , 1≤Ai≤10^9

Segment Tree implementation of the input array gets us the complexity of O(n) for creating the segment tree and O(log(n)) for queries. Overall Complexity- O(n+qlog(n))

Complexity for creating cartesian tree is O(n) and then for range queries we need to find the LCA of the 2 indices and the complexity for that is O(log(n)) Overall Complexity-O(n+qlog(n))

The segment tree implementation is doing good. But I am getting Time Limit Exceeded in the Cartesian Tree Implementation. Can anyone explain me the reason behind this?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English appro 2016-09-04 13:09:29 11
en1 English appro 2016-09-04 05:56:55 768 Initial revision (published)