Hi,

Problem
My solution

I made a segment tree with a slight modification to the merge function from merge sort. The recurrence should come to:

Which should be O(n lg n), for the initial building part. For each query it would take O(lg n) right? Why is this timing out? I made a huge test case and it kept running for like a minute. I tried fast i/o, tried to store results and output later, and converted the vector to list but nothing worked.

Is my analysis wrong? How do I make it faster? Please help.