Декомпозитсияи SQRT
Sqrt-decomposition як равиш барои татбиқи амалиётҳои ассотсиативӣ (масалан, ҷамъ кардани элементҳо, ёфтани ҳадди ақал/ҳадди аксар ва ғ.) дар элементҳои пайдарпайи ягон маҷмӯа бо андозаи дар барои ҳар як дархост мебошад.
Бигзор массиви бо андозаи дода шавад. Мо қадамҳои зеринро иҷро мекунем:
Агар мо -ро интихоб кунем, пас .
Мураккабӣ:
Фарз мекунем, ки мо дархосте мегирем, то амалиётеро дар қитъаи иҷро кунем. Қитъа метавонад баъзе блокҳои массиви -ро пурра пӯшонад ва ҳадди аксар ду блок (ибтидоӣ ва ниҳоӣ) — нопурра.
Пас, барои ёфтани натиҷаи амалиёт дар қитъаи , лозим аст онро дастӣ дар “думҳо” иҷро кунем ва баъд инро бо қиматҳои пешакӣ ҳисобшудаи блокҳои пурра якҷо намоем.
Дар поён мисол барои қитъаи оварда шудааст:
Мураккабӣ:
Вақте ки элемент дар мавқеи ба қимати нав навсозӣ мешавад, мо бояд қимати блоки мувофиқро дар навсозӣ кунем.
Элементи ба блоки
тааллуқ дорад.
Пас аз тағйир додани , мо қимати ҷамъбастии он блокро аз нав ҳисоб мекунем.
Мураккабӣ:
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];
}
}