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

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.

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

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??