Sparse table для gcd на отрезке — корректно ли, и чему равен нейтральный элемент?
Хочу отвечать на запросы «НОД (gcd) всех чисел на [l, r]» за O(1) через sparse table. gcd ведь идемпотентна (gcd(a,a)=a), значит трюк с перекрытием годится? И что брать нейтралью, если вдруг понадобится — 0 или 1?
2 ответа
Да, gcd идемпотентна: gcd(a, a) = a, поэтому обычная sparse table с перекрывающимися блоками работает корректно — двойной учёт элемента в пересечении безвреден. Реализация — как для min, только операция __gcd:
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] = __gcd(sp[j-1][i], sp[j-1][i + (1<<(j-1))]);
}
int query(int l, int r) {
int k = lg[r - l + 1];
return __gcd(sp[k][l], sp[k][r - (1<<k) + 1]);
}
Препроцессинг O(n log n · log(maxA)) (внутри __gcd ещё логарифм от значений), запрос O(log(maxA)) на сам __gcd (не совсем O(1), потому что gcd двух чисел не константа, но очень быстро).
Нейтральный элемент gcd — это 0, потому что gcd(0, x) = x. Единица не нейтраль: gcd(1, x) = 1 для любого x, что «съело» бы данные. Так что при пустом пересечении или инициализации возвращайте 0.
Уточню про «O(1)»: для min/max это честный O(1), а для gcd запрос — O(log(max_value)) из-за алгоритма Евклида внутри __gcd. На практике это всё равно крошечная константа, и sparse table остаётся отличным выбором для статичного gcd на отрезке.
Если же нужны обновления — sparse table не подойдёт (она статична), берите дерево отрезков с операцией gcd: слияние t[v] = __gcd(t[2v], t[2v+1]), нейтраль 0, обновление и запрос O(log n · log(maxA)).
Граabля с нейтралью 0 проявляется именно при пустых запросах и в дереве отрезков (возврат при l > r). Вернёте 1 вместо 0 — и любой отрезок, затрагивающий «пустую» ветку, даст gcd = 1. Запомните: для gcd нейтраль — ноль, потому что ноль делится на всё.