Sparse table (siyrak jadval)
Siyrak jadval (Sparse Table) — bu statik massiv (massiv o‘zgarmaydi) bo‘yicha kesma so‘rovlarini qayta ishlash uchun ma’lumotlar tuzilmasi.
Ko‘pincha quyidagilar uchun ishlatiladi:
Oldindan qayta ishlashdan so‘ng:
Har qanday sonni ikkilik darajalar yig‘indisi sifatida ifodalash mumkin:
Xuddi shuni kesma uzunligi bilan ham qilish mumkin.
Har qanday kesmani uzunligi bo‘lgan ikki ustma-ust tushuvchi kesmalar birlashmasi sifatida ifodalash mumkin:
Idemponent amallar (min, max, gcd) uchun bu juda yaxshi ishlaydi.
Jadval yaratamiz:
bu yerda:
i — kesmaning boshlanishij — ikkilik darajatable[i][j] i dan boshlanadigan, uzunligi bo‘lgan kesmadagi javobni saqlaydiBu turdagi uchun deb aniqlanadi. Jadval quyidagicha quriladi:
diapazoni uchun so‘rovga javob berish uchun biz barcha ikkilik darajalar bo‘ylab (eng kattasidan boshlab) o‘tamiz. Agar bo‘lsa, biz diapazonning birinchi qismi ni topdik va qolgan diapazon bilan davom etishimiz mumkin.
Siyrak jadval bunday turdagi so‘rovlarga murakkablik bilan eng yaxshi javob beradi. G‘oya shundan iboratki, yig‘indi so‘rovlaridan farqli ravishda, minimum diapazonlar ustma-ust tushmasligini talab qilmaydi, shuning uchun da ustma-ust tushmaydigan diapazonlarga bo‘lish o‘rniga, biz shunchaki diapazonni uzunligi 2 ning darajasi bo‘lgan 2 ta ustma-ust tushuvchi diapazonga bo‘lishimiz mumkin.
Masalan, diapazonini ko‘rib chiqaylik. Uni 7 da ustma-ust tushadigan va ga bo‘lish mumkin.
dan gacha bo‘lgan diapazon so‘roviga javob berish uchun biz bo‘ladigan eng katta ni topamiz va table[L][j] hamda table[R - 2^j + 1][j] ning minimumini qaytaramiz.
Oldindan qayta ishlash: , bu yerda — massiv o‘lchami.
Uzunligi bo‘lgan barcha kesmalar uchun qiymatlarni hisoblash talab etiladi.
So‘rovga javob:
Xotira: — ikkilik darajalarning barchasi uchun jadval saqlanadi.
Siyrak jadval quyidagi holatlarda samarali:
const int MAXN = 100000;
const int LOG = 20;
int table[MAXN][LOG];
int lg[MAXN];
int f(int a, int b) {
return min(a, b); // max, gcd va h.k. ga almashtirish mumkin
}
void buildSparseTable(int arr[], int N) {
// oldindan logarifmlarni hisoblaymiz
lg[1] = 0;
for (int i = 2; i <= N; i++) {
lg[i] = lg[i / 2] + 1;
}
// uzunligi 1 uchun initsializatsiya
for (int i = 0; i < N; i++) {
table[i][0] = arr[i];
}
// dinamik qurish
for (int j = 1; (1 << j) <= N; j++) {
for (int i = 0; i + (1 << j) <= N; i++) {
table[i][j] = f(
table[i][j - 1],
table[i + (1 << (j - 1))][j - 1]
);
}
}
}
void buildSparseTable(int arr[], int N) {
for (int i = 0; i < N; i++) {
table[i][0] = arr[i];
}
for (int j = 1; (1 << j) <= N; j++) {
for (int i = 0; i + (1 << j) <= N; i++) {
table[i][j] = table[i][j - 1] + table[i + (1 << (j - 1))][j - 1];
}
}
}
long long sum = 0;
// 2^25 odatda ko‘p masalalarda yetarli
for (int i = 25; i >= 0; i--) {
if ((1 << i) <= R - L + 1) {
sum += table[L][i];
L += (1 << i);
}
}
int query(int L, int R) {
int j = (int)log2(R - L + 1);
return min(table[L][j], table[R - (1 << j) + 1][j]);
}