Disjoint Sparse Table: всё за O(1)

Контест на codeforces: Мои реализации disjoint sparse table: Самая простая: Удобная версия с шаблонами: Без дополнения до степени двойки: Статья про дерево отрезков: Статья про sparse table (разреженная таблица): Хочу выразить огромную благодарность Гранту Сандерсу — автору канала 3blue1brown за вдохновение и за великолепную библиотеку manim, при помощи которой была сделана анимация в этом видео: Содержание: 00:00 - Вступление 00:30 - Постановка задачи количество минимумов на отрезке за O(1) 01:17 - Попробуем дерево отрезков 02:24 - Попробуем sparse table 03:41 - Идея алгоритма 06:51 - Как искать LCA в полном бинарном дереве? 08:09 - Битовая магия 08