Дизъюнктная sparse table (disjoint sparse table) — как она даёт O(1) для суммы?
Обычная sparse table не годится для суммы из-за двойного учёта перекрытия. Слышал про disjoint sparse table, которая решает это для любой ассоциативной операции. Как она устроена и почему запрос остаётся O(1)?
2 ответа
Идея: на уровне k массив делится на блоки длины 2^(k+1). Внутри каждого блока считаются префиксы/суффиксы от середины блока: суффиксы для левой половины, префиксы для правой. Тогда любой запрос [l, r] на нужном уровне попадёт так, что середина какого-то блока оказывается между l и r — и ответ = combine(суффикс[l], префикс[r]), два непересекающихся куска. Поэтому операция не обязана быть идемпотентной, только ассоциативной.
Как выбрать уровень: берём k такой, что l и r лежат в разных половинах блока размера 2^(k+1) — это определяется по старшему биту, в котором различаются l и r:
int level = lg[l ^ r]; // позиция старшего различающегося бита
return combine(table[level][l], table[level][r]);
(особый случай l == r обрабатываем отдельно — вернуть a[l]).
Построение: для каждого уровня проходим блоки, заполняя суффиксы влево от середины и префиксы вправо. Препроцессинг O(n log n) времени и памяти, запрос O(1). Это «честная» O(1)-структура для статичной суммы/произведения/любого ассоциативного моноида.
На олимпиадах disjoint sparse table нужна редко — обычно достаточно префиксных сумм (для суммы) или обычной sparse table (для min/max/gcd). Её ниша: статичные данные + ассоциативная, но не идемпотентная и без обратной операция. Примеры: произведение матриц по модулю, конкатенация хешей, объединение «слипающихся» структур.
Если же нужны обновления — sparse table (любая) не подходит вовсе, она статична. Тогда дерево отрезков: O(log n) на запрос и обновление. Сравнение по уму: sparse table выбирают исключительно ради O(1)-запроса на неизменном массиве; как только появляются модификации — переключайтесь на segment tree или Фенвик.