Rolling median solution
Integer math in tight loops is an area where C++ will definitely run circles around Python. I think your expectations are too high. However, I'd like to point out a couple of things for you, even if they are not enough to reach your goal.

Avoid indexing when you can use direct iteration instead. For example, insert can be written like this and Python won't have to deal with i:

def insert(tree,n):
     for level in tree:
         level[n] += 1
         n /= 2


Python does not optimize constant subexpressions out of loops, so you'll want to compute (K+1)/2 before the main loop and store it in a variable.