vjvjain0's blog

Find Median
By vjvjain0, 6 years ago, In English

Hey guys! I was doing a question and got an idea of this interesting question.

You are given an n size array a. The ith element of array a[i] is the frequency of the element. You are given q queries which has inputs left limit l and right limit r. You have to tell the median for the range.

1<=n<=10^6
1<=q<=10^5
1<=l<=n
1<=r<=n

Example:

Input:

5 2
4 7 9 1 2
1 2
3 5

Output:

2
3

Share your approaches in the comments. I don't if this is already a question on some online judge.

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

Comments Comments (3)
| Write comment?
»
6 years ago, # |
← Rev. 3   Vote: I like it -16 Vote: I do not like it

keep partial sums s[i] = a[1] + a[2] + ... + a[i], now the sum of frequences on range [l, r] is s[r] — s[l — 1]

the median on [l, r] is first position k in [l, r] such that a[l] + a[l + 1] + ... + a[k] is greater than a[l] + a[l + 1] + ... + a[r] / 2 + 1 <=> s[k] — s[l — 1] >= (s[r] — s[l — 1]) / 2 + 1 which can be found with binary search

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

    suppose a[l — r] = [1,2,3,1024], then sum of this range is 1024 + 6 = 1030, s/2 + 1 = 516...

    first element to do so is 4th element... ? am I missing something?

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

you can use persistent segment tree to find the k_th element where k = (r — l + 1) / 2 , and node i of the tree stores a[i].

→ Reply