SQRT dekompozitsiyasi
Sqrt-dekompozitsiya — bu o‘lchamli qandaydir to‘plamning ketma-ket elementlari ustida assotsiativ amallarni (masalan, elementlarni yig‘ish, minimum/maksimumni topish va h.k.) har bir so‘rov uchun da bajarish yondashuvidir.
o‘lchamli massivi berilgan bo‘lsin. Biz quyidagi qadamlarni bajaramiz:
Agar ni tanlasak, unda .
Murakkablik:
Faraz qilaylik, biz kesmasida amal bajarish so‘rovini olamiz. Kesma massivining ayrim bloklarini to‘liq qamrab olishi mumkin va ko‘pi bilan ikkita blokni (boshlang‘ich va yakuniy) — to‘liq emas.
Shunday qilib, kesmasida amal natijasini topish uchun uni “dumlar”da qo‘lda bajarish, so‘ng buni to‘liq bloklarning oldindan hisoblangan qiymatlari bilan birlashtirish zarur.
Quyida kesmasi uchun misol keltirilgan:
Murakkablik:
pozitsiyadagi element yangi qiymatga yangilanganda, biz dagi mos blok qiymatini yangilashimiz kerak.
elementi quyidagi blokka tegishli:
o‘zgartirilgandan so‘ng, biz o‘sha blokning agregat qiymatini qayta hisoblaymiz.
Murakkablik:
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];
}
}