Блог пользователя peltorator

Автор peltorator, 3 года назад, По-русски

Всем привет!

В новом видео мы поговорим про удивительную структуру данных Segment Tree Beats (Анимешное дерево отрезков), которая позволяет поддерживать огромное количество операций, с которыми не справляется обычное дерево отрезков. Узнаем, как брать числа на отрезке по модулю, применять операции min= и max=, добавлять к ним +=, а также еще и искать НОД на отрезке с этими операциями. Все это с понятными доказательствами, так что не бойтесь, все будет несложно! В следующей части мы рассмотрим еще больше удивительных запросов, так что не пропустите.

Ссылка на видео

There's also the English version of this video here

Буду рад, если вы посмотрите этот ролик и оставите комментарий со своими впечатлениями, замечаниями, мыслями и идеями насчет новых видео. Также можете написать мне в телеграм, если вы чего-то не поняли в видео или у вас возникли любые вопросы. Буду рад ответить!

Можете зайти на мой канал и посмотреть другие видео, если вы их еще не видели.

Контест с задчами на Segment Tree Beats.

Оригинальная статья на английском

Оригинальная статья на китайском

Реализации алгоритмов из этого видео:

%= на отрезке, = в точке, сумма на отрезке

Ji Driver Segment Tree (min= на отрезке, сумма на отрезке)

min= на отрезке, max= на отрезке, += на отрезке, = на отрезке, сумма на отрезке, минимум на отрезке, максимум на отрезке

Все то, что было в прошлой реализации, но еще и поиск НОДа на отрезке

P.S. Спасибо Golovanov399 за адаптацию названия.

  • Проголосовать: нравится
  • +374
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится -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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +25 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Спасибо за видео, очень образовательно!

Предлагаю на русском языке называть это анимешным деревом отрезков, а не ритмичным, потому что в анимешном я вижу больше смысла, а ещё это лучше характеризует источник названия и смешнее звучит, кмк

»
3 года назад, # |
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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -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.

»
3 года назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

The video is so nice and easy to understand!

You're a great video maker, for sure.

»
3 года назад, # |
  Проголосовать: нравится +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?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

»
19 месяцев назад, # |
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?

»
19 месяцев назад, # |
  Проголосовать: нравится 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 :)

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

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