Одномерные структуры данных (СПБГУ МатМех, весна 2013, спецкурс 344-й группы)

СНМ

1. Постановка задачи
2. Реализация за O(NlogN + M) --- color[v] и list[color], перекрашиваем меньший список
3. Реализация за O(1^*) --- сжатие путей и подвешивание меньшего к большему
4. Доказательство времени работы O(logN) для эвристики "подвешивание меньшего к большему"

RSQ и RMQ

1. Не меняющиаяся массив (длина N)
1. Сумма на префиксе за O(1)
2. Сумма на отрезке за O(1)
3. Минимум на префиксе за O(1)
4. Минимум на отрезке фиксированной длины за O(1)
5. Минимум на произвольном отрезке за O(1) с предподсчетом O(N²): min[l, r]
6. Минимум на произвольном отрезке за O(1) с предподсчетом O(NlogN): Sparse Table
2. Меняющиаяся массив (изменения типа a[i] := x)
1. Одномерное дерево отрезков (на массиве длины 2^k, с запросом снизу)
2. Отложенные операции для задачи произвольном
3. Не меняющиаяся матрица (ширина W, высота H)
1. Сумма в углу за O(1)
2. Сумма в прямоугольнике за O(1)
3. Минимум в углу за O(1)
4. Минимум в прямоугольнике фиксированного размера за O(1)
5. Минимум на произвольном прямоугольнике за O(1) с предподсчетом O(WHlogWlogH)

LCA

1. Полезный предподсчет: глубины вершин, время входа, время выхода
2. Проверить является ли a предком b за O(1)
3. Наивное решение за O(расстояния между вершинами)
4. Двоичные подъемы за O(NlogN) памяти и O(logN) времени
1. Реализация #1: сперва поднимаем нижнюю вершину до глубины верхней, затем прыгаем параллельно на 2^k
2. Реализация #2: поднимаем первую вершину на 2^k и за O(1) проверяем, попалили мы в предка второй
5. Сведение к RMQ за O(N)
6. Решение в Offline с СНМ за O((N+M)^*)

Одномерное дерево отрезков

1. Реализация снизу
1. Используем ровно 2N памяти
2. Построение за O(N)
3. Время ответа на запрос O(log(длины запроса))
4. Обрабатываем запросы: min(l, r) sum(l, r), change(i, x)
2. Реализация сверху
1. Используем до 4N памяти (можно соптимизить до 3N, но не меньше)
2. Построение за O(N)
3. Время ответа на запрос: не более 2logN просмотренных вершин
4. Запрос += на отрезке и min(l, r)
5. Запрос += на отрезке и sum(l, r)
6. Запрос = на отрезке и min(l, r)
7. Запрос = на отрезке и sum(l, r)