Введение в программирование 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 - Как нулевое число менять на ненулевое в обратном Фенвике на умножение?