AryanDLuffy's blog

Range queries of the form (l,r,x)
By AryanDLuffy, history, 5 years ago, In English

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).

  • Vote: I like it
  • -27
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AryanDLuffy (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Yes. It can be solved in O(logn) using Persistent Segment Tree.

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

this another way for solving your problem wavelet tree.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like 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.

→ Reply