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

*is the frequency of the element. You are given*

**a[i]****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.

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

This is a special case of SPOJ's MKTHNUM problem where k = range length/2. Solution is exactly the same.

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