Why do segment tree implementation give TLE in Chef and Strings???

general
,
1

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.

2

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

3

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

4

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.

5

Thanks. Now I get it.