Как быстро посчитать НОД на отрезке массива для многих запросов (sparse table)?
Дан массив, нужно отвечать на много запросов «НОД на отрезке [l, r]». Считать НОД заново каждый раз — O(n) на запрос, при q запросах слишком долго. Можно ли предобработать массив, чтобы запрос был быстрым? GCD же ассоциативен и идемпотентен.
2 ответа
Да — НОД идемпотентен (gcd(x, x) = x) и ассоциативен, поэтому для запросов на отрезке идеально подходит sparse table с ответом за O(1) на запрос (как для минимума/максимума). Идемпотентность позволяет перекрывать два блока без двойного учёта.
Предподсчёт: sparse[k][i] = НОД на отрезке длины 2^k, начинающемся в i.
int LOG;
vector<vector<int>> sp;
void build(const vector<int>& a) {
int n = a.size();
LOG = 1; while ((1 << LOG) <= n) LOG++;
sp.assign(LOG, vector<int>(n));
sp[0] = a;
for (int k = 1; k < LOG; k++)
for (int i = 0; i + (1 << k) <= n; i++)
sp[k][i] = __gcd(sp[k-1][i], sp[k-1][i + (1 << (k-1))]);
}
int query(int l, int r) { // НОД на [l, r], O(1)
int k = 31 - __builtin_clz(r - l + 1);
return __gcd(sp[k][l], sp[k][r - (1 << k) + 1]);
}
Построение — O(n log n) по времени и памяти, каждый запрос — O(1) (за счёт идемпотентности два перекрывающихся блока длины 2^k покрывают [l, r]). Это лучше дерева отрезков (O(log n) на запрос), если массив не меняется.
Если массив меняется между запросами (точечные обновления) — sparse table не подойдёт, бери дерево отрезков с операцией gcd в вершине: построение O(n), обновление и запрос по O(log n). Учти, что __gcd в каждой вершине дерева делается за O(log V), так что реальная стоимость запроса — O(log n · log V), где V — максимальное значение. Для статического массива sparse table практически всегда выгоднее.