Параллель А': различия между версиями
Материал из Algocode wiki
KiKoS (обсуждение | вклад) |
KiKoS (обсуждение | вклад) |
||
Строка 47: | Строка 47: | ||
* [[RMQ в окне]] | * [[RMQ в окне]] | ||
* [[Sparse Table]] | * [[Sparse Table]] | ||
+ | * [[Disjoint Sparse Table]] | ||
* [[LCA]] | * [[LCA]] | ||
* [[Алгоритм Фарака-Колтона и Бендера|$RMQ \pm 1$]] | * [[Алгоритм Фарака-Колтона и Бендера|$RMQ \pm 1$]] | ||
Строка 52: | Строка 53: | ||
* [[Сжатые деревья]] | * [[Сжатые деревья]] | ||
* [[Heavy-light decomposition]] | * [[Heavy-light decomposition]] | ||
− |
Версия 11:52, 16 октября 2019
Содержание
1. Корневая оптимизация
- Корневая декомпозиция
- Корневая на строках
- Корневая в задачах на графы
- split-rebuild
- split-merge
- Корневая по запросам
- Алгоритм Мо
2. Геометрия 1
- Тут тоже что-то есть, но добавлено будет позже
3. Структуры данных 1
- Дерево отрезков
- Декартово дерево
- Дерево Фенвика
- Merge sort tree
- Отложенные операции
- Динамические структуры данных
- Двумерные структуры данных
4. Оптимизации динамики
- Монотонность точки перегиба
- Divide&Conquer оптимизация
- Оптимизация Кнута
- Convex hull trick
- Дерево Li Chao
- Лямбда-оптимизация
- $\text{MOD}^2$-оптимизация
5. Математика 1
- Алгоритм Евклида
- Расширенный алгоритм Евклида
- Диофантово уравнение
- Обратный по модулю
- Решето Эратосфена
- Линейное решето Эратосфена
- Обратные ко всем остаткам за O(p)