Введение в программирование 10. Дерево Фенвика, двумерный Фенвик, обратный Фенвик

Введение в программирование, алгоритмы и структуры данных. МФТИ, Физтех-школа прикладной математики и информатики

Лекция прочитана 11 ноября 2021 года
Лектор: Степанов Илья Даниилович
Оператор: Мария Шкатова
Монтаж: Жильцов Игорь

0:00 - Дерево Фенвика
5:35 - Сумма на префиксе в Фенвике
8:32 - Асимптотика. Объяснение функции i & (i + 1)
15:00 - Обновление в точке. Функция i | (i + 1)
29:54 - Почему мы взяли именно такие функции?
36:32 - Построение. Алгоритмы за O(n log n) и O(n)
40:12 - Обобщение на большие размерности
45:05 - Двумерный Фенвик
47:11 - Двумерная префиксная сумма
52:21 - Обновление в точке в двумерном Фенвике
56:11 - Замечание про асимптотику построения двумерного Фенвика
58:13 - Другие операции, поддерживаемые Фенвиком. Произведение
1:00:58 - Максимум. Обратное дерево Фенвика
1:15:10 - Код процедуры getMax
1:20:08 - Упражнение: увеличение в точке обратного Фенвика
1:26:42 - Какие операции умеет поддерживать Фенвик?
1:28:10 - Как нулевое число менять на ненулевое в обратном Фенвике на умножение?