peltorator's blog

Video: Segment Tree Beats
By peltorator, 4 years ago, translation, In English

Hi!

In the new video, we’re going to talk about the amazing data structure called Segment Tree Beats, which allows us to support a huge number of operations that a regular segment tree can’t handle. We will learn how to take numbers on a segment modulo some number, apply the min= and max= operations, add += to them, and also find GCD on a segment with these operations. And all the proofs are gonna be super simple, so don’t be scared, it will be easy! In the next video, we will cover even more awesome queries, so stay tuned.

Link to the video

You can check out my previous videos on my channel

Contest on Segment Tree Beats (and others) is here

Also, there's the Russian version of this video if you speak Russian here

Original article in English

Original article in Chinese

Implementations of algorithms from this video:

%= on a segment, = in a point, sum on a segment

Ji Driver Segment Tree (min= on a segment, sum on a segment)

min= on a segment, max= on a segment, += on a segment, = on a segment, sum on a segment, minimum on a segment, maximum on a segment

Everything from the previous implementation but also GCD on a segment of algorithms from this video:

%= on a segment, = in a point, sum on a segment

Ji Driver Segment Tree (min= on a segment, sum on a segment)

min= on a segment, max= on a segment, += on a segment, = on a segment, sum on a segment, minimum on a segment, maximum on a segment

Everything from the previous realisation but also GCD on a segment

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

Comments Comments (20)
| Write comment?
»
4 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Wow man this is real content, and by that I mean not just like repetitive topics being repeated by almost every new YouTuber which makes it confusing at times.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

    Thanks! I try to bring something new. But different perspectives on well-known ideas are also important in my opinion. I often watch videos on topics I know well and pretty much always find there something fresh for me.

    → Reply
»
4 years ago, # |
  Vote: I like it -73 Vote: I do not like it

This went over my head. Please make some lectures for guys with rating range 1600-1900. Thanks. By the way, you explain very well, I have watched your previous videos.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +95 Vote: I do not like it

    Dude there are 998244353 resources for people in that rating range already, while there are almost none for IMs and above. Please stop hijacking threads.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      In the past 7 hours, it increased by $$$1757654$$$. The number for IMs hasn't increased.

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

we’re going to talk about the amazing data structure called Segment Tree Beats (an Anime Segment Tree)

why this part is omitted in the english version of this post lol

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Segment Tree Beats is the English name and the second one is the Russian version of it.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -19 Vote: I do not like it

      Let's call it Weeb Segment Tree in English. At least this name gives us some information about the author, while the word "beats" it just useless.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -28 Vote: I do not like it

        Ok downvoters, keep on living with shitty naming

        → Reply
»
4 years ago, # |
  Vote: I like it +39 Vote: I do not like it

The video is well-prepared and the explanation is crystal-clear, bravo!

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

The video is so nice and easy to understand!

You're a great video maker, for sure.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

As far as I can remember, I have recently seen a video about Farah-Colton and Bender algorithm on you channel and now I can't find it. Am I mistaken or just can't find it or is it deleted now?

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

Notice that $$$= x$$$ on seg $$$\Leftrightarrow$$$ combination of $$$min= \ x $$$ and $$$max= \ x$$$ on seg. This makes implementation easier.

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have two very similar codes(first, second). The only difference is that in the first code there is a restriction $$$l==r$$$ in tag condition. It gets AC, but if I remove that extra restriction, it gets WA9(second submission).

Any idea why that happens?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    because if you stop when l != r, you need to have push values and lazy propagate them later

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Oof, I missed that. Thanks!

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

In E, why in doPushSum do we have to check if min==max for a node? Why can't we just add as we do if min!=max? What changes?

Sorry for pinging peltorator, but I don't understand it :)

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Are you talking about my solution? IDK, maybe we shouldn't. But this case where all the numbers are equal is just tricky so I checked it everywhere to be sure.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      I couldn't get AC without that part btw. Thanks for the answer!

      → Reply