Hi I have been trying to solve this problem http://www.spoj.com/problems/KL11B/ The solution I have found so far uses BIT + Treap(Balanced Tree) and worst case complexity is log^2(n) for each query. Some users have accepted the problem using a lot less time and memory than other users that I know they used this solution. Is there a faster solution to this problem or it was just constant optimization?, would there be a faster to code solution to this problem having at most log^2(n) complexity for each query.