Блог пользователя AryanDLuffy

Range queries of the form (l,r,x)
Автор AryanDLuffy, история, 4 года назад, По-английски

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

  • Проголосовать: нравится
  • -27
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

this another way for solving your problem wavelet tree.

→ Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      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.

      → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить