Flattening the tree and using a Persistent Segment Tree worked for me. However, the constraints were a bit harsh and I had to remove some redundant queries and replace some other queries (like queries over entire range) with pre-computed values to squash the constant time factor.
Here’s my O(n*logn) solution: CodeChef: Practical coding for everyone