- Range Sum Query (RSQ)
- Постановка задачи
- Реализация за $O(1), O(n)$
- Реализация за $O(n^2), O(1)$
- Реализация за $O(n), O(1)$ с использованием частичных сумм
- Range Min Query (RMQ)
- Постановка задачи
- Реализация за $O(1), O(n)$
- Реализация за $O(n^2), O(1)$
- Реализация $O(n \log{n}), O(1)$ с использованием разреженных таблиц
- Типы задач
- Offline-задачи
- Online-задачи
- Задачи с изменением элементов
- Деревья интервалов (отрезков)
- Структура дерева интервалов и представление в памяти
- Построение дерева интервалов за линейное время
- Решение задач RMQ и RSQ на дереве интервалов за $O(\log{n})$
- Реализация сверху вниз (рекурсивная)
- Реализация снизу вверху (итеративная)
- Изменение элементов
- Изменение одного элемента
- Добавление и вычитание на отрезке
- Ассоциативные операции
- Определение ассоциативной операции
- Минимум и сумма как ассоциативные операции
- Примеры ассоциативных операций
- Ассоциативные операции и деревья отрезков
|