### sigmamale's blog

By sigmamale, history, 2 months ago,

Hi. I am reading Efficient and easy segment trees(bottom-up approach) and I solved a problem "Assignment to Segment" from edu(the problem is about interval assign). But I can't prove why it's sufficient to propagate only parents of l and r - 1. Can anybody help me to prove it? Problem link

My code

• +5

 » 2 months ago, # |   -8 Your question was really helpful for me. I will try to give you a direction to think.Firstly I understand your question this way — when asked to assign v from l to r, why is it sufficient to lazily push values for ancestors of l and r only and then perform our operation?So I drew out a 8 sized segment tree(you try too) and saw for different queries how your algorithm works. Specifically for the push function. You will see that the pushed values for l if go to the left, are not changed and the right ones get updated while doing our update operation. Similar thing happens with r also.hope it helps clarify things. Alternate approach for this problemAs you can see assignment operation is not just non-commutative but also that only the latest assignment matters. So you can just store time of some operation and make a normal commutative type segtree. Just for the point query you take latest assignments from all the parents and the 'combine' operation combines two elements and gives out the more recent element.
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 I already drew 8 and 16 sized segment tree and I see that "The right ones get updates while doing our update operation", but that only kinda rephrases my question. Why do we only update the right ones, maybe in a some X sized segment tree we will modify a node whose parent wasn't pushed, I see that never happens, but I can't find a proof for that.
 » 2 months ago, # | ← Rev. 2 →   +3  //interval = [L, R) for (int l = L + n, r = R + n; l < r; l >>= 1, r >>= 1) { if (l&1) res += t[l++]; if (r&1) res += t[--r]; } Let S be the set of nodes "making up" the interval [L, R). Notice for all nodes k ∈ S: k's parent's interval ⊈ [L, R) (otherwise it's better to take k's parent).Now consider if l&1 is true at some depth (so l ∈ S). It's enough to show that l's parent is an ancestor of leaf L (since then, every ancestor of l is an ancestor of leaf L, so propagating all ancestors of leaves L, R-1 is the same as propagating all ancestors of all nodes ∈ S).Let l's parent's interval be [par_l, par_r). We know [par_l, par_r) ⊈ [L, R) (so either par_l < L or R < par_r).But since l is odd, it is the right child of l's parent (so their intervals share a right-endpoint). Since l's interval ⊆ [L, R): par_r <= R. So par_l < L. So L ∈ l's parent's interval. So l's parent is an ancestor of leaf L.
•  » » 2 months ago, # ^ |   0 I got it, thank you