Структура данных, навсегда изменившая мир к худшему 🤯
В этом видео разбираем дерево отрезков: как оно устроено, чем отличается от корневой декомпозиции, как обрабатывает запросы на НОД, сумму и максимум. Реализуем его на C++ и добавляем поддержку операций над отдельными элементами: присваивание и прибавление. В конце смотрим, как Питер Фенвик радикально упростил дерево отрезков на сумму, выкинув ненужные узлы и перенумеровав оставшиеся, и получил структуру данных, которую позже назвали деревом Фенвика. Тайм-коды: 00:00:00 Введение 00:01:46 Чем корневая декомпозиция отличается от дерева отрезков 00:02:30 Как устроено дерево отрезков 00:09:45 Процесс обработки запроса вычисления функции на отрезке 00:16:05 Асимптотика обработки запроса 00:20:55 Решаем задачу "A. НОД на отрезке" 00:23:40 Реализуем дерево отрезков в C++ 00:32:30 Сколько узлов нужно выделить для дерева отрезков? 00:39:50 Продолжаем реализовывать дерево отрезков 00:49:49 Сдаём задачу 00:50:20 Разбираем исходный код решения на C++ целиком 00:56:35 Задача "D. НОД с изменением элемента" 00:57:00 Как реализовать присваивание в дереве отрезков 01:04:25 Компилируем и сдаём 01:06:40 Задача "B. RSQ с изменением элемента" 01:09:25 Задача "C. RMQ с изменением элемента" 01:13:21 Решаем задачу "E. Range Maximum Query" первым способом 01:22:10 Сдаём задачу вторым способом 01:27:27 Задача "F. Дерево с изменением отрезка" 01:28:05 Первый способ: разностный массив 01:34:30 Разбираем исходный код решения на C++ 01:36:45 Второй способ: через обновление узлов и сумму на пути от листьев до корня 01:46:50 Третий способ: дерево Фенвика. Как Фенвик упростил дерево отрезков 01:58:58 Завершение
В этом видео разбираем дерево отрезков: как оно устроено, чем отличается от корневой декомпозиции, как обрабатывает запросы на НОД, сумму и максимум. Реализуем его на C++ и добавляем поддержку операций над отдельными элементами: присваивание и прибавление. В конце смотрим, как Питер Фенвик радикально упростил дерево отрезков на сумму, выкинув ненужные узлы и перенумеровав оставшиеся, и получил структуру данных, которую позже назвали деревом Фенвика. Тайм-коды: 00:00:00 Введение 00:01:46 Чем корневая декомпозиция отличается от дерева отрезков 00:02:30 Как устроено дерево отрезков 00:09:45 Процесс обработки запроса вычисления функции на отрезке 00:16:05 Асимптотика обработки запроса 00:20:55 Решаем задачу "A. НОД на отрезке" 00:23:40 Реализуем дерево отрезков в C++ 00:32:30 Сколько узлов нужно выделить для дерева отрезков? 00:39:50 Продолжаем реализовывать дерево отрезков 00:49:49 Сдаём задачу 00:50:20 Разбираем исходный код решения на C++ целиком 00:56:35 Задача "D. НОД с изменением элемента" 00:57:00 Как реализовать присваивание в дереве отрезков 01:04:25 Компилируем и сдаём 01:06:40 Задача "B. RSQ с изменением элемента" 01:09:25 Задача "C. RMQ с изменением элемента" 01:13:21 Решаем задачу "E. Range Maximum Query" первым способом 01:22:10 Сдаём задачу вторым способом 01:27:27 Задача "F. Дерево с изменением отрезка" 01:28:05 Первый способ: разностный массив 01:34:30 Разбираем исходный код решения на C++ 01:36:45 Второй способ: через обновление узлов и сумму на пути от листьев до корня 01:46:50 Третий способ: дерево Фенвика. Как Фенвик упростил дерево отрезков 01:58:58 Завершение