Лекция 3. Дерево Фенвика
HTML-код
- Опубликовано: 1 окт 2024
- Андрей Гейн: Это лекция о структуре данных, которая позволяет для массива чисел быстро находить сумму на подотрезке этого массива и при этом не использовать дополнительную память. Субъективная сложность лекции - две теты из пяти.
Содержание:
13:17 Префиксные суммы
18:36 Сложность операций и длины подотрезков
36:58 Двумерная визуализация
46:50 Оптимальные длины подотрезков
1:16:36 Изменение элементов
1:28:50 Почему дерево Фенвика - это дерево
1:32:28 Многомерные префиксные суммы
1:37:26 Построение дерева Фенвика
Самое понятное объяснение этой темы!
Андрей крутой
Котан запутался в терминах на ~ 59:00 -> 1:02:00 а в остальном шикарный шикос
Самая топ лекция по данной теме. Преподаватель отлично все разжевал с конкретными примерами. Просто топ!
Шикарный лектор. Нереально круто объясняет. Спасибо
Да, отличная лекция.
Гениально!
Не зря потратил полтора часа своей жизни. Во всём разобрался, спасибо.
Это очень крутая лекция. Настолько понятно и доступно
Спасибо за материал, было все понятно!
Спасибо вам большое за столь понятное объяснение!
Спасибо, что разложили озы в самом начале. Про отрезки, бинарные операции. Все постепенно сложилось в общую картину.
Спасибо!
Добрый день! не очень хочется портить отзывы, проделана большая работа НО, есть ряд неточностей - (видимо никто после Вашей лекции не писал код) - во первых, при нахождении суммы Вы дали неверный расчет следующего индекса (index = (index&(index + 1)) - 1) и еще - Вы говорите ,что это представление не дерево. Это дерево с представлением в виде массива с корнем и способом движения от корня к потомкам, как и любое другое дерево. (классическая задача - бинарное дерево поиска в массив и формула нахождения потомков i*2 , i*2 + 1) Ну и особенности дерева Фенвика для нахождения минимума на отрезке не упоминаются вообще.