Disjoint Sparse Table: всё за O(1)
The English version is below. Привет! Я Егор. В этом видео я рассказываю про структуру данных, которая называется disjoint sparse table. Она очень красивая, однако по ней мало информации можно найти в интернете. Надеюсь, это видео вам покажется полезным. На этом канале я собираюсь делать анимированные видео, объясняющие разные алгоритмы и структуры данных. Я собираюсь затронуть как самые базовые темы: префиксные суммы, бинарный поиск, сортировки; так и продвинутые: segment tree beats, heavy-light декомпозиция, link-cut tree, лямбда-оптимизация, FFT и другие. Если вам это интересно, подписывайтесь на канал :) Можете предлагать темы, на которые вы хотели бы увидеть видео, в комментариях к этому видео или лично мне в телеграме. Также можете писать мне, если чего-то не поняли или у вас есть какие-то вопросы. С радостью отвечу! Успехов на контестах! Контест на codeforces: https://codeforces.com/group/1rv4rhCs...
Мои реализации disjoint sparse table: Самая простая: https://pastebin.com/wc1FsZri
Удобная версия с шаблонами: https://pastebin.com/iDFUGN2S
Без дополнения до степени двойки: https://pastebin.com/uaWg4Awk
Статья про дерево отрезков: https://e-maxx.ru/algo/segment_tree
Статья про sparse table (разреженная таблица): https://neerc.ifmo.ru/wiki/index.php?...
Хочу выразить огромную благодарность Гранту Сандерсону — автору канала 3blue1brown за вдохновение и за великолепную библиотеку manim, при помощи которой была сделана анимация в этом видео: https://github.com/3b1b/manim
/ @3blue1brown Также хочу поблагодарить моих друзей, которым пришлось отсматривать это длинное видео и оставлять свои пожелания и комментарии. Благодаря вам оно стало намного лучше! Содержание: 00:00 - Вступление 00:30 - Постановка задачи количество минимумов на отрезке за O(1) 01:17 - Попробуем дерево отрезков 02:24 - Попробуем sparse table 03:41 - Идея алгоритма 06:51 - Как искать LCA в полном бинарном дереве? 08:09 - Битовая магия 08:43 - Первый отличающийся бит 09:27 - Поиск старшего бита числа 09:54 - __builtin_clz 10:36 - Как хранить disjoint sparse table? 13:54 - Код построения disjoint sparse table 16:40 - Код запроса к disjoint sparse table 17:11 - Произведение на отрезке за O(1) 18:59 - Произведение матриц на отрезке за O(1) 19:32 - Количество подпоследовательностей шаблонов на отрезке за O(1) 24:49 - Самая дорогая подпоследовательность шаблон на отрезке за O(1) 32:21 - Заключение Мои контакты: telegram: https://t.me/peltorator
codeforces: https://codeforces.com/profile/peltor...
instagram: / peltorator The English version: Codeforces contest: https://codeforces.com/group/1rv4rhCs...
My disjoint sparse table realisations: Easy one: https://pastebin.com/wc1FsZri
Easy to use with templates: https://pastebin.com/iDFUGN2S
Without extending to the power of two: https://pastebin.com/uaWg4Awk
An article about segment tree: https://cp-algorithms.com/data_struct...
An article about sparse table: https://cp-algorithms.com/data_struct....
I want to thank Grant Sanderson (the author of the 3blue1brown youtube channel) for inspiration and the brilliant manim library, this video was made with: https://github.com/3b1b/manim
/ @3blue1brown Hi! My name is Egor. In this video, I'm talking about a data structure named disjoint sparse table. It's really beautiful, but it's hard to find any information about it on the internet. I hope you find this video helpful. I'm gonna make more videos in the future. Both on basic algorithms such as prefix sums, binary search, sorting, etc., and also some advanced topics such as segment tree beats, heavy-light decomposition, link-cut tree, lambda optimization, FFT, and so on. If you're interested, consider subscribing to my channel! If you have any questions you can contact me on telegram. Good luck with your contests. Reach me out on: telegram: https://t.me/peltorator
codeforces: https://codeforces.com/profile/peltor...
instagram: / peltorator Or peltorator at any platform
