I want to solve this problem with top-down splay tree but i don't know how to maintain the sum of the nodes' left subtree , could anyone tell me how to deal with it ? ?
Thanks very much ! !

i implemented splay trees once for school thew were intersting.... but u would be better of with interval trees they are easier to implement and come in handy a lot