sigmamale's blog

By sigmamale, history, 7 weeks ago, In English

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
  • Vote: I like it
  • +5
  • Vote: I do not like it

7 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

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 problem
  • »
    7 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

7 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it
  //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 kS: 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 lS). 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 Ll's parent's interval. So l's parent is an ancestor of leaf L.