Всем привет!
В новом видео мы поговорим про удивительную структуру данных Segment Tree Beats (Анимешное дерево отрезков), которая позволяет поддерживать огромное количество операций, с которыми не справляется обычное дерево отрезков. Узнаем, как брать числа на отрезке по модулю, применять операции min= и max=, добавлять к ним +=, а также еще и искать НОД на отрезке с этими операциями. Все это с понятными доказательствами, так что не бойтесь, все будет несложно! В следующей части мы рассмотрим еще больше удивительных запросов, так что не пропустите.
There's also the English version of this video here
Буду рад, если вы посмотрите этот ролик и оставите комментарий со своими впечатлениями, замечаниями, мыслями и идеями насчет новых видео. Также можете написать мне в телеграм, если вы чего-то не поняли в видео или у вас возникли любые вопросы. Буду рад ответить!
Можете зайти на мой канал и посмотреть другие видео, если вы их еще не видели.
Контест с задчами на Segment Tree Beats.
Оригинальная статья на английском
Оригинальная статья на китайском
Реализации алгоритмов из этого видео:
%= на отрезке, = в точке, сумма на отрезке
Ji Driver Segment Tree (min= на отрезке, сумма на отрезке)
Все то, что было в прошлой реализации, но еще и поиск НОДа на отрезке
P.S. Спасибо Golovanov399 за адаптацию названия.
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.
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.
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.
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.
In the past 7 hours, it increased by $$$1757654$$$. The number for IMs hasn't increased.
Спасибо за видео, очень образовательно!
Предлагаю на русском языке называть это анимешным деревом отрезков, а не ритмичным, потому что в анимешном я вижу больше смысла, а ещё это лучше характеризует источник названия и смешнее звучит, кмк
Ахах, это гениально, Я поддерживаю!
why this part is omitted in the english version of this post lol
Segment Tree Beats is the English name and the second one is the Russian version of 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.
Ok downvoters, keep on living with shitty naming
The video is well-prepared and the explanation is crystal-clear, bravo!
Thanks! It means the world to me.
The video is so nice and easy to understand!
You're a great video maker, for sure.
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?
Notice that $$$= x$$$ on seg $$$\Leftrightarrow$$$ combination of $$$min= \ x $$$ and $$$max= \ x$$$ on seg. This makes implementation easier.
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?
because if you stop when l != r, you need to have push values and lazy propagate them later
Oof, I missed that. Thanks!
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 :)
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.
I couldn't get AC without that part btw. Thanks for the answer!