minh0722's blog

Lazy segment tree for modification of range of elements in an array in log(n) complexity
By minh0722, history, 3 weeks ago, In English

Just learned new data structure for problem G. Penacony that makes use of lazy segment tree in order to solve it.

References: https://www.youtube.com/watch?v=iMjd2QI6NEs (from this comment)

https://www.scaler.com/topics/data-structures/segment-tree-with-lazy-propagation/

https://codeforces.net/blog/entry/131528

  • Vote: I like it
  • +9
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

  1. this doesn't need lazy, u just made a problem, a harder one for no reason: 278260614.

  2. Why learn it as this stage? I mean yeah it sounds cool, a segment tree, an advanced data structure that can do almost anything on ranges of an array, All in O(log), but, a harsh truth: A segment tree won't solve a problem, it'll make a solved problem implementable, u don't solve problem using it, u solve problems and code it using it. So knowing it won't come in handy unless u know how to solve problems, and by problems I mean Div 2 E+, maybe sometimes D(although there usually exists one without it (1976D - Invertible Bracket Sequences), So learning it will just fill ur mind with useless things, and make solving problems harder since u just think of: is there anything that I can do with segment, I've seen ppl do div2 B with segment when it's all just a prefix sum.

→ Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    Why learn it as this stage?

    Because it's interesting! No one should ever need a reason to learn things.

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I think of it as learning another new tool in my toolbox, not as a universal Swiss knife for everything.

    Also it's the point of exercising these problems, to learn new things!

    → Reply
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    That's a bad take, especially when the editorial has Lazy Segment Trees as the main solution. Sure, you can cheese it with normal segment trees, but is it worth it?

    In the video, I also mention that learning lazy segment trees is not required for this problem, if you are a beginner, you can just write a wrapper that does whatever lazy segtree is supposed to do, but slower. And the video talks about how to use it as a black box using Atcoder library, not the internal details of lazy segtree.

    Suppose in the next contest you encounter an inversion counting problem, would you solve it using Merge sort technique or using Segment/Fenwick tree? Sure, you can carefully implement merge sort, but what about the person that used Fenwick and scored more points than you. Is that fair? Of course it is. Make sure you're playing to win, no matter the tactics as long as it is legal. A lot of people seem to play their own version of the game, but then act surprised when they don't see results.

    A similar argument is for people who took coaching to improve in a hobby field like Competitive Programming. For some reason, people love to dunk on the people who had a lot of help while growing in this field, because everything was provided to them, while you came from scratch and built your empire. But what did it cost you? Your invaluable time. But the person who took coaching won in both aspects, they saved precious time of their life to devote to other priorities, and they are at least as good as you. Remember that Codeforces ratings doesn't care about where you come from. If you're able to solve problems, you are in, else you're out.

    → Reply