Segment Tree Beats: Дерево Отрезков На Стероидах. Часть 1

73 Просмотры

Спасибо! Поделитесь с друзьями!

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

Издатель May 8, 2021

If you speak English here is the English version of this video: https://youtu.be/NwkO73jGSPA

Привет! Я Егор. Я учусь в СПбГУ, занимаюсь спортивным программированием и очень люблю алгоритмы. В этом видео я рассказываю про структуру данных, которая называется Segment Tree Beats (либо Анимешное Дерево Отрезков на русском), которая помогает решить огромный пласт задач, с которыми не справляется обычное дерево отрезков. Мы рассмотрим несколько интересных задач, в том числе взятие по модулю на отрезке, Ji Driver Segment Tree и его вариации с операцией прибавления на отрезке и взятия НОДа на отрезке. Надеюсь, это видео вам покажется полезным. На этом канале я делаю анимированные видео, объясняющие разные алгоритмы и структуры данных. Я затрагиваю как самые базовые темы: префиксные суммы, бинарный поиск, сортировки; так и продвинутые: disjoint sparse table, heavy-light декомпозиция, link-cut tree, лямбда-оптимизация, FFT и другие. Если вам это интересно, подписывайтесь на канал :) Можете предлагать темы, на которые вы хотели бы увидеть видео, в комментариях к этому видео или лично мне в телеграме. Также можете писать мне, если чего-то не поняли или у вас есть какие-то вопросы. С радостью отвечу! Успехов на контестах!

Контест на codeforces: https://codeforces.com/group/1rv4rhCsHp/contests

Оригинальная статья на английском: https://codeforces.com/blog/entry/57319

Оригинальная статья на китайском: http://www.doc88.com/p-6744902151779.html

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

%= на отрезке, = в точке, сумма на отрезке: https://pastebin.com/wabDfjKi

Ji Driver Segment Tree (min= на отрезке, сумма на отрезке): https://pastebin.com/bEEQsDr7

min= на отрезке, max= на отрезке, += на отрезке, = на отрезке, сумма на отрезке, минимум на отрезке, максимум на отрезке: https://pastebin.com/UJhuFA3a

Все то, что было в прошлой реализации, но еще и поиск НОДа на отрезке: https://pastebin.com/jDMC5R2T

Хочу выразить огромную благодарность Гранту Сандерсону — автору канала 3blue1brown за вдохновение и за великолепную библиотеку manim, при помощи которой была сделана анимация в этом видео:

https://github.com/3b1b/manim

https://www.youtube.com/channel/UCYO_jab_esuFRV4b17AJtAw

Содержание:
00:00 - Вступление
01:25 - Общая идея Segment Tree Beats
04:26 - tagCondition и breakCondition
08:33 - Операция %= на отрезке
11:45 - Обычные, дополнительные и тупиковые вершины
16:20 - Ji Driver Segment Tree (min= на отрезке)
20:14 - Продвинутый Ji Driver Segment Tree (min=, += на отрезке)
24:50 - Операция += на отрезке, поиск НОДа на отрезке
28:45 - Операции += и min= на отрезке, поиск НОДа на отрезке
31:40 - Заключение

Мои контакты:

telegram:

https://t.me/peltorator

codeforces:

https://codeforces.com/profile/peltorator

instagram:

https://www.instagram.com/peltorator/