Statement

Is it possible to solve this question using splay trees (without using any sort of randomization)?

I have tried the following:-

• Treaps (isolate range for query): TLE Code

• Treaps (query by traversing BST): AC Code

• Splay (isolate range for query): TLE Code

• Splay (query by traversing BST): TLE Code (This one fails when all the updates are before the queries.The updates might lead to a straight chain BST even with splaying. And since the query by traversing BST never calls splay(), every query takes linear time)

Suggestions please. An AC code (Splay Tree only) would be really helpful.