### peltorator's blog

By peltorator, 12 months 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

 » 12 months 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.
•  » » 12 months 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.
 » 12 months 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.
•  » » 12 months 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.
•  » » » 12 months ago, # ^ |   +25 In the past 7 hours, it increased by $1757654$. The number for IMs hasn't increased.
•  » » » 12 months ago, # ^ |   -15 My rating has been fluctuating from 1750 to 1850 for last 6 months so I asked for it. Why such negativity? Are you 2300 on cf? Lol
 » 12 months 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
•  » » 12 months ago, # ^ |   +8 Segment Tree Beats is the English name and the second one is the Russian version of it.
•  » » » 12 months 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.
•  » » » » 12 months ago, # ^ |   -28 Ok downvoters, keep on living with shitty naming
•  » » » » » 12 months ago, # ^ |   0 It should be :"Segment tree Weebs" instead of Weeb segment tree,........that's why we downvoted you : ) It just sounds better. gives us some information about the author Why do you need that anyways?
 » 12 months ago, # |   +39 The video is well-prepared and the explanation is crystal-clear, bravo!
•  » » 12 months ago, # ^ |   +21 Thanks! It means the world to me.
 » 12 months ago, # |   +10 The video is so nice and easy to understand!You're a great video maker, for sure.
 » 12 months 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?
 » 9 months ago, # | ← Rev. 2 →   +5 Notice that $= x$ on seg $\Leftrightarrow$ combination of $min= \ x$ and $max= \ x$ on seg. This makes implementation easier.