### chor123's blog

By chor123, history, 12 days ago,

I want to find out time complexity and space complexity of this code.

https://cses.fi/paste/4c432ea7de710eac40593c/

I was trying to solve this task but I was getting TLE.

 » 12 days ago, # |   +22 Wow, you really have no clue. I guess you just think that segment tree is magic.Time complexity is $O(n \log^2 n + qn \log n)$, space complexity is $O(n \log n + qn)$ ($qn$ part might not be true, I'm not sure how is it measured).