TTMMM's blog

Do i really need lazy propagation in segment tree question( range updates)?
By TTMMM, history, 5 years ago, In English

How important is lazy propagation in competitive programming? It takes me a lot of time to implement it. How do i get to know weather it is required or not by looking at the constraints? I mean, what is the complexity of a algorithm with and without it?

  • Vote: I like it
  • -24
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Consider all you updates happen on the whole array, without lazy propagation you'll have to update values in $$$O(N)$$$ nodes for each query, so segment tree will be useless.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it

Doing range updates naively will yield a $$$O(QN)$$$ complexity which will usually render using a segment tree useless for most problems. Complexity depends on the problem and type of lazy propagation, but the simplest ones (e.g. set value, add value) add only constant overload on the tree and hence keep a logarithmic complexity per query.

I'd argue that in higher levels of competitive programming lazy propagation is an extremely essential tool that one must be able to code quickly and without having to give it much thought. For Div2 it is probably not as crucial.

Why does it take you a lot of time to implement it? Occasionally you need some clever stuff, but in the majority of the cases the code to add lazy propagation is essentially the same and really short.

P.S.

To address the question in the title: If you want to be good, you most definitely do.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There are some cases when you need not use lazy propagation, smartly using fenwick tree will also suffice for range updates and query, online.

→ Reply