Блог пользователя TTMMM

Автор TTMMM, история, 5 лет назад, По-английски

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?

  • Проголосовать: нравится
  • -24
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
5 лет назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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