### vjvjain0's blog

By vjvjain0, 6 months ago, ,

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:

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.

•
• -11
•

 » 6 months ago, # | ← Rev. 3 →   -16 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
 » 6 months ago, # | ← Rev. 3 →   0 This is a special case of SPOJ's MKTHNUM problem where k = range length/2. Solution is exactly the same.
 » 6 months ago, # | ← Rev. 3 →   0 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].