### peltorator's blog

By peltorator, 21 month(s) ago, translation,

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.

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

• +374

| Write comment?
 » 21 month(s) ago, # |   +31 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.
•  » » 21 month(s) ago, # ^ |   +56 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.
 » 21 month(s) ago, # |   -73 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.
•  » » 21 month(s) ago, # ^ |   +95 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.
•  » » » 21 month(s) ago, # ^ |   +25 In the past 7 hours, it increased by $1757654$. The number for IMs hasn't increased.
 » 21 month(s) ago, # | ← Rev. 2 →   -18 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
•  » » 21 month(s) ago, # ^ |   +8 Segment Tree Beats is the English name and the second one is the Russian version of it.
•  » » » 21 month(s) ago, # ^ |   -19 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.
•  » » » » 21 month(s) ago, # ^ |   -28 Ok downvoters, keep on living with shitty naming
 » 21 month(s) ago, # |   +39 The video is well-prepared and the explanation is crystal-clear, bravo!
•  » » 21 month(s) ago, # ^ |   +21 Thanks! It means the world to me.
 » 21 month(s) ago, # |   +10 The video is so nice and easy to understand!You're a great video maker, for sure.
 » 21 month(s) ago, # |   +3 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?
 » 18 months ago, # | ← Rev. 2 →   +5 Notice that $= x$ on seg $\Leftrightarrow$ combination of $min= \ x$ and $max= \ x$ on seg. This makes implementation easier.
 » 5 months ago, # | ← Rev. 2 →   0 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?
•  » » 5 months ago, # ^ |   +8 because if you stop when l != r, you need to have push values and lazy propagate them later
•  » » » 5 months ago, # ^ |   +10 Oof, I missed that. Thanks!
 » 5 months ago, # |   0 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 :)
•  » » 5 months ago, # ^ |   +8 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.
•  » » » 5 months ago, # ^ |   +10 I couldn't get AC without that part btw. Thanks for the answer!