### yaksha's blog

By yaksha, history, 4 years ago,

Hi, So this has happened before , and it happens from time to time , only this time I really got frustrated and hence am asking this question . . Why is my segment tree so slow?

Some problems like this -> 301D - Yaroslav and Divisors , have the official solution, the same as the solution that I code but somehow my segment tree is always very slow. This has happened before in live contests as well . Maybe my implementation is very bad , that's why I want to learn where I am making mistake , and please provide me with a better implementation if I am making a mistake..

My implementation to the above problem,using segment trees, which TLE's --> 36075338 . Help me out on this please!

UPDATE: I solved the problem doing some minor optimizations like scanf/printf and using int instead of long long , but my solution is still very slow compared to other solutions..

• +8

 » 4 years ago, # |   +11 Try to do not use ll while it does not need, because it doubles your calculations.
•  » » 4 years ago, # ^ |   +2 Thanks for the tip , I tried that and earlier my code TLE'd on test 24 .. .Now it TLE's on test 35 , definitely an improvement but still lacking :(36076125
 » 4 years ago, # |   +11 There's much faster iterative version of segment tree, refer this.
 » 4 years ago, # |   +1 Did you try using scanf and printf ?
•  » » 4 years ago, # ^ |   +3 I just did and it passed , but look how slow it is -->36076672Other solutions are WAY faster than this , despite the fact that I am not using long long and also using printf and scanf , my solution runs in 1400 ms while several others run in 800ms , this makes a huge difference in contests!
 » 4 years ago, # | ← Rev. 2 →   +3 I think you should use 'long long' when you need, and if you want to speed up, use 'scanf' and 'printf' instead of 'cin' and 'cout'. Or you can read more about 'Lazy update of Segment Tree'.
•  » » 4 years ago, # ^ |   0 ofc I can do these things but that's not my point , there are other solutions out there similar to mine , no one of them uses lazy update but still run faster , ~800ms while mine runs in 1400ms , after a lot of small optmizations
 » 4 years ago, # | ← Rev. 3 →   +3 endl -> "\n" remove pragmas
•  » » 4 years ago, # ^ |   +3 Sorry I dont know much about pragmas , but aren't the first few lines supposed to fasten my solution a little bit?
•  » » » 4 years ago, # ^ |   0 I know that pragmas will speed up your solution if simple operations are present
•  » » » 4 years ago, # ^ |   +3 remove the Ofast pragma, keep the other two. Ofast has only been bad in my experience, but the processor optimizations won't be harmful, they have only ever given me speed increase or no change.
 » 4 years ago, # |   0 Auto comment: topic has been updated by yaksha (previous revision, new revision, compare).
 » 4 years ago, # |   +3 Don't use endl unless its an interactive problem. move the update tree[id] upwards(before recursive call) as you always know how much it will increase. This will allow tail-recursion optimization. inline your left and right functions
 » 4 years ago, # |   0
•  » » 4 years ago, # ^ |   0 okay so "\n" and cin.tie and cout.tie make so much difference! , Noted
 » 4 years ago, # |   +3 Your query function may degrade into O(n) behavior. Try changing it.
•  » » 4 years ago, # ^ |   0 How exactly?
•  » » 4 years ago, # ^ |   0 can you elaborate more please?!
•  » » » 4 years ago, # ^ | ← Rev. 5 →   +8 Sure.Your query only terminates when l and r perfectly matches up with x and y. At worst case these will be the leaf nodes. This is O(n).A way to fix this is to add code which immediately terminates when your segment is completely within or completely without.if (l > y || r < x) return null; //some invalid valueif (l >= x && r <= y) return tree[id];Hope this helps.
•  » » » » 4 years ago, # ^ |   0 The values before calling the query function are actually changed to fit the boundaries of the node that is being called. Read the query function again. I don't think what you've said can happen in this code.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Sorry I did not make myself clear.I meant the modified [x,y] (as it keeps cutting down by 2) because in the worst case this will terminate when it becomes the leaf nodes and only encompass a single element. Such a query would be O(n).