How to keep track of the median of changing vector of integers?

Question

Trying to solve a problem at http://www.hackerearth.com/problem/algorithm/sum-of-medians-1/ and thought to solve it using the multiset as it may contain duplicate values. I tried to code as follows:

#include<iostream>
#include<set>
#include<algorithm>
using namespace std;
int main()
{
  int n,k,med_sum=0,p;
  cin>>n;
  multiset<int> m;
  multiset<int>::iterator itr;
  for(int i=0;i<n;i++)
  {
    cin>>k;
    m.insert(k);
    p=k;
    if(p<=k)
      itr--;
    else
      itr++;
    med_sum+=*itr;
  }
  cout<<med_sum<<endl;
  return 0;
}

---

Sample Input:
n=5
10
5
1
2
15
Sample Output: 27
Explanation:
m(1)=median of [10]=10
m(2)=median of [10 5]=5
m(3)=median of [10 5 1]=5
m(4)=median of [10 5 1 2 15]=5
med_sum=10+5+5+2+5=27

Answer 1

An easy way to do this is to maintain two sorted containers, one lower than the median, one greater.

When you find a new element, see what container to insert it into (so that all elements of lower are always less than or equal to all elements of upper), then rebalance counts so that the median is "in the gap" between them.

Yours sort of does this, but defines the lower range to be [.begin(), it) and the upper to be [it, .end()). I'd make them separate containers to reduce the amount of state you need to keep in your head to understand the code, unless performance was particularly important.

Maintain two sorted containers, low and high, with the following invariants:

• low.size() is the same as high.size() or 1 larger
• Every element of low is less than or equal to every element of high. Then the median of low union high is low.last().

Assuming you have such a pair of containers, if you wanted to add an element x, I would first maintain invariant 2 -- if low.empty() or x <= low.last(), stick it in low, otherwise stick it in high.

Next, maintain invariant 1: if high has more elements than low, remove the lowest element from high and add it to low. If low has 2 more elements than high, remove the highest element from low and add it to high.

If we started with a low and high that obeyed the above two invariants, then after the above steps we still have a low and high that obeys these two invariants. And when the above two invariants hold, the median is low.last()!