| 1 |
Суффиксный автомат (англ. suffix automaton, directed acyclic word graph) — минимальный детерминированный конечный автомат, который принимает все суффиксы строки и только их. |
| 2 |
Декартово дерево или дерамида (англ. Treap) — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: treap (tree + heap) и дерамида (дерево + пирамида), также существует название курево (куча + дерево). |
| 3 |
Link-cut tree — это структура данных, которая хранит лес деревьев и позволяет выполнять следующие операции: min(v) — искать минимум на пути от вершины до корня, add(v,c) — прибавлять константу на пути от вершины до корня, link(u,w) — подвешивать одно дерево на другое, cut(v) — отрезать дерево с корнем в вершине v. Среднее время выполнения каждой операции — O(logn). Эта структура данных была придумана Робертом Тарьяном и Даниелем Слейтером в 1982 году. |
| 4 |
Дерево отрезков (англ. Segment tree) — это структура данных, которая позволяет за асимптотику O(logn) реализовать любые операции, определяемые на множестве, на котором данная операция ассоциативна, и существует нейтральный элемент относительно этой операции, то есть на моноиде. Например, суммирование на множестве натуральных чисел, поиск минимума на любом числовом множестве, перемножение матриц на множестве матриц размера N*N, объединение множеств, поиск наибольшего общего делителя на множестве целых чисел и многочленов. |
Комментарии