Статические варианты задач RMQ, RSQ, LCA. Плюс дучи (декартовы деревья).

Лекция посвящена асимптотически оптимальным структурам данных для статических вариантов задач RMQ (range minimum query), RSQ (range sum query), LCA (least common ancestor). Также, в начале лекции подробно рассказывается про такую структуру данных как “дуча“, также известную как “декартово дерево“. В английской терминологии данная структура имеет названия treap (tree heap) и cartesian tree.