SQRT Декомпозиция
Sqrt-декомпозиция — это подход к реализации ассоциативных операций (например, суммирование элементов, нахождение минимума/максимума и т. д.) на последовательных элементах некоторого множества размера за на запрос.
Пусть дан массив размера . Выполним следующие шаги:
Если выбрать , тогда .
Сложность:
Предположим, мы получаем запрос на выполнение операции на отрезке . Отрезок может полностью покрывать некоторые блоки массива , и не более двух блоков (начальный и конечный) — не полностью.
Таким образом, чтобы найти результат операции на отрезке , необходимо выполнить её вручную на «хвостах», а затем объединить это с предварительно вычисленными значениями полных блоков.
Ниже приведён пример для отрезка :
Сложность:
Когда элемент в позиции обновляется до нового значения, мы должны обновить соответствующее значение блока в .
Элемент принадлежит блоку
После изменения мы пересчитываем агрегированное значение этого блока.
Сложность:
for (int i = 0; i < M; i++) {
b[i] = 0;
for (int j = i * K; j < min(N, (i + 1) * K); j++) {
b[i] = b[i] + a[j];
}
}
int query(int l, int r) {
int left_block = l / K;
int right_block = r / K;
int res = 0;
if (left_block == right_block) {
for (int i = l; i <= r; i++) {
res += a[i];
}
} else {
for (int i = l; i < (left_block + 1) * K; i++) {
res += a[i];
}
for (int i = left_block + 1; i < right_block; i++) {
res += b[i];
}
for (int i = right_block * K; i <= r; i++) {
res += a[i];
}
}
return res;
}
void update(int i, int new_a) {
int block = i / K;
a[i] = new_a;
b[block] = 0;
for (int j = block * K; j < min(N, (block + 1) * K); j++) {
b[block] += a[j];
}
}