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?
Cartesian tree is slower than segment tree because of constant that appears from "Merge" and "Split" functions. For example, if you want to insert some element, you need split your tree by key and merge. It means that operaton works O(2*log(N)).