Can anyone help me implement lazy propogation in this segment tree code??
i just can’t get it.
ok, try this
1: use binary index tree to update value
2: make use of this fact that a number will be reduced to 1 (by repetitive square root operation) in around 5-6 max operations
so for an x to y, don’t traverse from x to y, use some branching technique like
take an example… query is 2 to 9 and i know 4,5,6,7 are already reduced to 1…
i’ll execute this query as…
reduce 2 to its square root … what is next of 2… ok 3
reduce 3 to its square root … what is next of 3 which is not 1, ok 8
reduce 8 to its square root … what is next of 8 which is not 1, ok 9
reduce 9 to its square root … i am done with query.
so initial queries will take time but slowly they’ll get reduce.
hope so i explained properly? 
if i didn’t please ask where i was not clear
Enjoy 
1 Like
the problem is that the update operations are over a given interval [a;b]. Let us consider that we have some number in the array K = 1<<64 = 18446744073709551616. This is quite big in fact and there might not be any numbers so big.
sqrt(1<<64) = 1<<32, sqrt(1<<32) = 1<<16, sqrt(1<<16) = 1<<8, …sqrt(1<<1) = 1<<0 = 1, sqrt(1<<1) = 1. Just after 7 operations we reached the bottom. So what can happen in the worst case if we do update operations over each element. We will just do 7 * n*log(n) updates and then we won’t to do any at all. => we can approach the updates naively, but if we have only 1s in a given segment, then we shouldn’t do any updates since this won’t change anything because sqrt(1) = 1.
For this, void update(int idx, int sfrom, int sto, int qfrom, int qto) {long long ss = (long long)sto - (long long)sfrom + 1LL; if (tree[idx].sum == ss) return;… rest update function}
i guess you are using inbuilt sqrt function for updating the array that is leading to TLE… try some faster sqrt calculations. 
1 Like
This too is giving TLE
getting TLE repeatedly guys…it would be great if anyone can tell me how would i get accepted.
Why can’t segment Tree be used here??
well, i am not getting how are you updating a range for an update query…
as in i used lazy propagation in queries like…
i have to set some value for each node… or something ,somewhere i have some pattern
i am not getting how you are updating a range… thats why i used BIT
1 Like
well here we can’t use lazy propagation because sqrt(x1+x2)!=sqrt(x1)+sqrt(x2)
yeah… right! , this is what i was saying
So, here we can’t use segment tree(no lazy propagation)… did you get AC with BIT??