Структуры данных: различия между версиями
Материал из Algocode wiki
KiKoS (обсуждение | вклад) м |
Gmusya (обсуждение | вклад) |
||
(не показано 9 промежуточных версий 4 участников) | |||
Строка 1: | Строка 1: | ||
==Структуры данных из STL== | ==Структуры данных из STL== | ||
+ | * [[Стек]] | ||
+ | * [[Очередь]] | ||
+ | * [[Дек]] | ||
==Структуры данных для запросов на отрезке== | ==Структуры данных для запросов на отрезке== | ||
* [[Sparse Table]] | * [[Sparse Table]] | ||
+ | * [[Дерево отрезков]] | ||
+ | * [[Дерево Фенвика]] | ||
+ | * [[Декартово дерево]] | ||
+ | * [[Динамические структуры данных]] | ||
+ | * [[Отложенные операции]] | ||
+ | * [[Merge sort tree]] | ||
==Сканирующая прямая== | ==Сканирующая прямая== | ||
Строка 9: | Строка 18: | ||
==Корневые оптимизации== | ==Корневые оптимизации== | ||
+ | * [[Корневая декомпозиция]] | ||
+ | * [[Корневая декомпозиция на массиве]] | ||
* [[Корневая на строках]] | * [[Корневая на строках]] | ||
+ | * [[Корневая в задачах на графы]] | ||
+ | * [[split-rebuild]] | ||
+ | * [[split-merge]] | ||
+ | * [[Корневая по запросам]] | ||
+ | * [[Алгоритм Мо]] | ||
+ | * [[Рюкзак за Ssqrt|Рюкзак за $O(S \sqrt{S})$]] | ||
==Структуры данных в задачах на деревья== | ==Структуры данных в задачах на деревья== | ||
+ | |||
+ | * [[Centroid декомпозиция]] | ||
+ | * [[Link-cut tree]] | ||
==Многомерные структуры данных== | ==Многомерные структуры данных== | ||
* [[Sparse Table#Несколько измерений|Многомерные Sparse Table]] | * [[Sparse Table#Несколько измерений|Многомерные Sparse Table]] | ||
+ | * [[Дерево Фенвика#Многомерный случай|Многомерный Фенвик]] | ||
+ | * [[Двумерные структуры данных]] | ||
==Продвинутые применения структур данных для запросов на отрезке== | ==Продвинутые применения структур данных для запросов на отрезке== | ||
Строка 24: | Строка 46: | ||
==Двоичные деревья поиска== | ==Двоичные деревья поиска== | ||
+ | * [[Декартово дерево]] | ||
+ | * [[Splay-дерево]] |
Текущая версия на 17:05, 2 марта 2021
Содержание
- 1 Структуры данных из STL
- 2 Структуры данных для запросов на отрезке
- 3 Сканирующая прямая
- 4 Корневые оптимизации
- 5 Структуры данных в задачах на деревья
- 6 Многомерные структуры данных
- 7 Продвинутые применения структур данных для запросов на отрезке
- 8 Персистентность
- 9 Кучи
- 10 Двоичные деревья поиска
Структуры данных из STL
Структуры данных для запросов на отрезке
- Sparse Table
- Дерево отрезков
- Дерево Фенвика
- Декартово дерево
- Динамические структуры данных
- Отложенные операции
- Merge sort tree
Сканирующая прямая
Корневые оптимизации
- Корневая декомпозиция
- Корневая декомпозиция на массиве
- Корневая на строках
- Корневая в задачах на графы
- split-rebuild
- split-merge
- Корневая по запросам
- Алгоритм Мо
- Рюкзак за $O(S \sqrt{S})$