Segment Tree Beats: Segment Tree на стероидах. Часть 1

Привет! Меня зовут Егор. В этом видео я рассказываю о структуре данных под названием Segment Tree Beats. Она помогает решать множество задач, с которыми не справляется обычное дерево сегментов. Мы рассмотрим несколько интересных задач, таких как взятие всех чисел на отрезке по модулю некоторого числа, Ji Driver Segment Tree и его вариации со сложением на отрезке, а также вычисление НОД на отрезке. Надеюсь, это видео будет вам полезным. В будущем я планирую снять ещё больше видео. Как по базовым алгоритмам, таким как префиксные суммы, двоичный поиск, сортировка и т.д., так и по более сложным темам, таким как непересекающиеся разреженные таблицы, тяжело-лёгкая декомпозиция, дерево с разрезами, лямбда-оптимизация, БПФ и так далее. Если вам интересно, подписывайтесь на мой канал! Если у вас есть вопросы, свяжитесь со мной в Telegram. Удачи в ваших конкурсах. Конкурс Codeforces:
Если вы говорите по-русски, вот русская версия этого видео:    • Segment Tree Beats: Дерево Отрезков На Сте...   Оригинальная статья на английском:
Оригинальная статья на китайском:
Реализации алгоритмов из этого видео: %= на отрезке, = в точке, сумма на отрезке:
Дерево сегментов драйвера Цзи (min= на отрезке, сумма на отрезке):
min= на отрезке, max= на отрезке, += на отрезке, = на отрезке, сумма на отрезке, минимум на отрезке, максимум на сегменте:
Всё из предыдущей реализации, а также НОД на сегменте:
Хочу поблагодарить Гранта Сандерсона (автора канала 3blue1brown на YouTube) за вдохновение и великолепную библиотеку manim. Это видео было создано с помощью:
   / @3blue1brown   Главы: 00:00 - Введение 01:43 - Общая идея битов дерева сегментов 05:19 - tagCondition и breakCondition 10:06 - Операция %= на сегменте 14:13 - Общие, дополнительные и тупиковые вершины 19:40 - Дерево сегментов драйвера Ji (min= на сегменте) 24:27 - Расширенный Ji Дерево сегментов драйверов (min=, += на сегменте) 30:25 — Операция += на сегменте, НОД на сегменте 35:33 — Операции += и min= на сегменте, НОД на сегменте 39:25 — Заключение Свяжитесь со мной: telegram:
codeforces:
instagram:   / peltorator   Или peltorator на любой платформе