АиСД S02E03. Разреженная таблица. Дерево Фенвика
Vložit
- čas přidán 22. 02. 2022
- Алгоритмы и структуры данных. Семестр 2. Лекция 3.
На третьей лекции мы рассмотрели еще несколько важных структур данных для обработки запросов на отрезках: разреженную таблицу и дерево Фенвика.
Университет ИТМО, 2022 г.
А какой структурой можно искать минимум на отрезке с препроцессингом O(n) и константным временем на запрос?
czcams.com/video/ISxV-um8TYw/video.html
я правильно понимаю, что построение дерева фенвика мы будем производить с помощью функции inc() при этом быстрее чем n*log(n) мы дерево построить не сможем? просто я почему, то ожидал, что сложность как и у дерева отрезков будет линейной...
Можно построить за O(n)
@@pavelmavrin ну да, действительно. можно построить массив префиксных сумм, а уже по ним построить фенвика. ну в моем случае t - массив дерева фенвика. то t[i] = prefix[i] - prefix[f(i) - 1]. ну и естественно все это линейно при условии f(i) - считает за O(1) ....
16:31 Нужно быть очень аккуратным и правильно расставить скобки, на питоне, к примеру, i & (i + 1) - 1 и (i & (i + 1)) - 1 дают разные результаты