Sparse table для RMQ за O(1): почему только идемпотентные операции?
Реализовал sparse table для минимума на отрезке: препроцессинг O(n log n), запрос O(1) через два перекрывающихся блока. Работает. Но почему этот трюк с перекрытием годится для min/max/gcd и НЕ годится для суммы? Что за «идемпотентность»?
2 ответа
Идемпотентность операции ∘ значит x ∘ x = x. Для min это так: min(a, a) = a. Для max и gcd тоже. Для суммы — нет: a + a = 2a ≠ a.
Запрос O(1) в sparse table устроен так: берём наибольшую степень двойки k = floor(log2(len)) и накрываем [l, r] двумя перекрывающимися блоками длины 2^k: [l, l+2^k-1] и [r-2^k+1, r]. Эти блоки пересекаются (если len не степень двойки). Для min перекрытие безвредно — элементы в пересечении учтутся дважды, но min(x, x) = x ничего не портит. Для суммы перекрытие посчитает общую часть дважды → неверный результат.
int sp[LOG][N], lg[N+1];
void build(int n) {
lg[1] = 0;
for (int i = 2; i <= n; ++i) lg[i] = lg[i/2] + 1;
for (int i = 0; i < n; ++i) sp[0][i] = a[i];
for (int j = 1; (1<<j) <= n; ++j)
for (int i = 0; i + (1<<j) <= n; ++i)
sp[j][i] = min(sp[j-1][i], sp[j-1][i + (1<<(j-1))]);
}
int query(int l, int r) { // min на [l, r]
int k = lg[r - l + 1];
return min(sp[k][l], sp[k][r - (1<<k) + 1]);
}
Сложность: build O(n log n) по времени и памяти, query O(1). Идеально для статичных данных (без обновлений).
Для суммы есть отдельный приём — disjoint sparse table (дизъюнктная разреженная таблица), которая разбивает [l, r] на два непересекающихся куска, поэтому работает для любой ассоциативной операции, не только идемпотентной. Запрос тоже O(1), препроцессинг O(n log n). Но реализация заметно сложнее обычной sparse table.
На практике для суммы со статичными данными чаще берут просто префиксные суммы — O(n) препроцессинг, O(1) запрос, тривиально. Sparse table для суммы оправдан, когда операция «как сумма» по типу, но обратной операции нет (например, перемножение матриц по модулю), и тогда disjoint sparse table — правильный инструмент.