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