I don’t understand why segment tree implementation gives TLE for chef and strings(STRQ). Here is the link to my code. Please have a look. http://ideone.com/62RGET

Precomputation gets AC.

I don’t understand why segment tree implementation gives TLE for chef and strings(STRQ). Here is the link to my code. Please have a look. http://ideone.com/62RGET

Precomputation gets AC.

Segment tree in NlogN buiding time + logN query while pre computation takes linear building time and constant query time. So thats why!

Building time of segment tree is O(n) and n in this question is 10^6, so O(nlogn) should work fine in 1 sec

O(nlog(n)) works fine with 10^5, not 10^6.

Since the number of queries are 10^6, you need a constant time algo.

Thanks. Now I get it.