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..
Try to do not use ll while it does not need, because it doubles your calculations.
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
There's much faster iterative version of segment tree, refer this.
Did you try using scanf and printf ?
I just did and it passed , but look how slow it is -->
36076672
Other 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!
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'.
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
endl -> "\n"
remove pragmas
Sorry I dont know much about pragmas , but aren't the first few lines supposed to fasten my solution a little bit?
I know that pragmas will speed up your solution if simple operations are present
remove the
Ofastpragma, keep the other two.Ofasthas 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.Auto comment: topic has been updated by yaksha (previous revision, new revision, compare).
36081515
okay so "\n" and cin.tie and cout.tie make so much difference! , Noted
Your query function may degrade into O(n) behavior. Try changing it.
How exactly?
can you elaborate more please?!
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 value
if (l >= x && r <= y) return tree[id];
Hope this helps.
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.
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).