Алгоритмы и структуры данных — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 69: Строка 69:
 
* [[Дерево Фенвика для некоммутативных операций]]
 
* [[Дерево Фенвика для некоммутативных операций]]
 
* [[Многомерное дерево Фенвика]]
 
* [[Многомерное дерево Фенвика]]
 +
 +
== Задача о наименьшем общем предке ==
 +
* [[Алгоритм Мо]]
 +
* [[Сведение задачи LCA к задаче RMQ]]
 +
* [[Сведение задачи RMQ к задаче LCA]]
 +
* [[Метод двоичного подъема]]
 +
* [[Решение RMQ с помощью разреженной таблицы]]
 +
* [[Двумерная разреженная таблица]]
 +
* [[Алгоритм Фарака-Колтона и Бендера]] (решение +/-1 RMQ с помощью метода четырех русских)
 +
* [[Алгоритм Хьюи]]
 +
* [[Heavy-light декомпозиция]]
 +
* [[Алгоритм Шибера-Вишкина]]<tex>^\star</tex>
 +
* [[Алгоритм Тарьяна поиска LCA за O(1) в оффлайн]]<tex>^\star</tex>
 +
* [[Link-Cut Tree]]<tex>^\star</tex>
 +
* [[Rake-Compress деревья]]<tex>^\star</tex>
  
 
== Хеширование ==
 
== Хеширование ==

Версия 13:46, 24 февраля 2017

Амортизационный анализ

Персистентные структуры данных

Приоритетные очереди

Система непересекающихся множеств

Поисковые структуры данных

Дерево отрезков

Дерево Фенвика

Задача о наименьшем общем предке

Хеширование

Сортировки

Квадратичные сортировки

Сортировки на сравнениях

Многопоточные сортировки

Другие сортировки

Сортирующие сети

Алгоритмы поиска

Связь между структурами данных