Can range queries of form (l,r,x) where the answer to the query is number of values less than x in range [l,r] of a given array be solved in O(logn) time online? There are no updates. Plz describe the solution if it exists. I know of the solution by merge sort tree which solves it in O((logn)^2).
Auto comment: topic has been updated by AryanDLuffy (previous revision, new revision, compare).
Yes. It can be solved in O(logn) using Persistent Segment Tree.
Can you plz explain in detail how to do so?
this another way for solving your problem wavelet tree.
Thanks, will see.
If you don't know about Persistent Segment Tree, you can read it here.
WLOG, we can assume that all the elements in the array are less than 1e5(If they are more than 1e5 you can compress it).
Now, at each position of the array used for creating the tree, you can store the sum of frequencies of all elements from (l, r) which represents the node.
Can you plz describe more? I mean with it I see it is easy to get the kth order range statistics but how to answer the mentioned query?
We are building a segment tree using the sum of frequency that occurred until index i(which would be stored in the root[i] where root[i] is the root of segment tree built at index i).
WLOG, let's assume the query is (l, r, x). So basically we would only concentrate on root[r] and root[l — 1]. Also, let's assume that the compressed value of x is y.
So the query is reduced to find sum of frequencies of numbers from [1, y] between two roots(root[r], root[l — 1]) which can easily be obtained as we are maintaining sum segment tree.
Thanks for the reply. I got it.
One idea comes to mind. Keep track of the count of the maximum number in the segment[lo, hi], then during the query, the result should be: number of elements in the segment — (number of Maximus)) or (r-l + 1 — (query(l, r)).
To keep track the number of maximums in the range we can use segment tree.
Plz mention if something is wrong.
x can be greater than the maximum value in range. I believe it is wrong.
yeah, right!! Can you provide the link..
Link for what?
Above question.