bipulkmr2016's blog

Range median query.
By bipulkmr2016, history, 8 years ago, In English

How to solve range queries for median efficiently as asked in this question. https://www.codechef.com/CDJA2016.

  • Vote: I like it
  • +3
  • Vote: I do not like it

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

http://stackoverflow.com/questions/26296624/order-statistic-on-intervals

Hope this helps.

EDIT:

Read the highest rated answer for the general idea — using a segment tree to store sorted ranges. Instead of using nested binary searches like they proposed, you can do a binary search for the answer itself — you guess a number X and then search the sorted ranges (again using binary search) to see if the number is above, below, or is the median. The complexity is log(n) ^ 3 per search, although this can be improved.

This is just a rough sketch, if you need a better explanation let me know.

There's also a problem on SPOJ http://www.spoj.com/problems/MKTHNUM/

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    yes, I got the idea but i could not get how the space is 0(nlog(n)).please elaborate.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      In every level of the segment tree there are N elements in total and the tree's height is O(logN) so the memory is O(NlogN).

      UPD: Sorry, I used nodes instead of elements :)

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

Since N ≤ 103 and Q ≤ N2 simply precompute answer for each interval [L;R] with any BBST in O(N2logN), then answer queries in O(1).

This can make your implementation easier: http://codeforces.com/blog/entry/11080 .

Code: http://pastebin.com/meVxg99E .

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

    Yes, that would be the more appropriate solution for that particular problem. The precomputing step can actually be done in O(N^2). Hint: use linked lists

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

      how to solve it?? using linked list

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

        Let's reformulate the problem.

        The median of an array A is the floor(n / 2)-th element of sort(A).

        You have an array B and you must find the median element for every prefix of B.

        The solution to this problem:

        Create a sorted doubly-linked list of all elements of A, and for each element of A keep the pointer to the corresponding node in the list. This step can be done in O(NlogN).

        We now want to track the k-largest element using a pointer, let's call that pointer "middle". Initially just find the floor(n / 2)-th element in the list. For the median problem, the value of k changes but that's not a big issue as we're about to see.

        Starting from the end of A, remove elements one by one from the list. Each time you remove a number from the list, adjust the pointer accordingly — if the number removed was before the "middle" you need to move "middle" to the next node in the list. Otherwise do not move "middle".

        Now, when the value of k decreases, for example, this happens when we used to have 8 elements and after removing one we have 7, the value of k changes from 4 to 3 and again we need to adjust "middle". It's simple — when k decreases just move "middle" to the previous node of the list.

        To solve the main problem just apply the above algorithm to every suffix of A. Note that you can obtain the N sorted linked lists for every suffix of A in O(n2) time.

        Hope this was clear enough :)

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

In Russian there is a nice explanation of how to do such a thing in on-line in per query: http://codeforces.com/blog/entry/2954?locale=ru#comment-59840

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

watch this https://www.youtube.com/watch?v=6x4-lfhHd_Y

→ Reply