It seems like they are using a really weird data structure (it's not even clear whether it's sub-quadratic).

This is a textbook problem normally solved using a balanced binary tree augmented by adding a number with the size of the subtree to every node (an "order statistic tree").