Ҷадвали пароканда
Ҷадвали пароканда (Sparse Table) — ин сохтори додаҳо барои коркарди дархостҳо дар порча аз рӯи массиви статикӣ (массив тағйир намеёбад) мебошад.
Бештар вақт истифода мешавад барои:
Пас аз коркарди пешакӣ:
Ҳар як ададро метавон ҳамчун ҷамъбасти дараҷаҳои ду ифода кард:
Ҳаминро бо дарозии порча низ кардан мумкин аст.
Ҳар як порчаи -ро метавон ҳамчун иттиҳоди ду порчаи ҳампӯш бо дарозии ифода кард:
Барои амалиётҳои идемпотентӣ (min, max, gcd) ин комилан кор мекунад.
Ҷадвал месозем:
ки дар он:
i — оғози порчаj — дараҷаи дуtable[i][j] ҷавобро дар порчаи дарозии , ки аз i оғоз мешавад, нигоҳ медорадБарои ин навъи чунин муайян мешавад: . Ҷадвал ба таври зерин сохта мешавад:
Барои ҷавоб додан ба дархост барои диапазони , ба мо лозим аст аз ҳамаи дараҷаҳои ду (аз калонтаринаш сар карда) гузарем. Агар , мо қисми якуми диапазон -ро ёфтем ва метавонем бо диапазони боқимонда идома диҳем.
Ҷадвали пароканда беҳтарин ба чунин навъи дархостҳо бо мураккабии ҷавоб медиҳад. Идея дар он аст, ки бар хилофи дархостҳои ҷамъ, минимум талаб намекунад, ки диапазонҳо ҳампӯш нашаванд, бинобар ин ба ҷои он ки ба диапазонҳои беҳампӯш дар тақсим кунем, мо метавонем танҳо диапазонро ба 2 диапазони ҳампӯш бо дарозии дараҷаи 2 тақсим кунем.
Масалан, диапазони -ро баррасӣ мекунем. Онро метавон ба ва тақсим кард, ки дар 7 ҳампӯш мешаванд.
Барои ҷавоб додан ба дархости диапазон аз то , мо калонтарин -ро меёбем, ки чунин аст ва минимумро аз table[L][j] ва table[R - 2^j + 1][j] бармегардонем.
Коркарди пешакӣ: , ки дар он — андозаи массив аст.
Лозим аст қиматҳоро барои ҳамаи порчаҳои дарозии ҳисоб кунем.
Ҷавоб ба дархост:
Хотира: — ҷадвал барои ҳамаи дараҷаҳои ду нигоҳ дошта мешавад.
Ҷадвали пароканда самаранок аст, вақте ки:
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 и т.д.
}
void buildSparseTable(int arr[], int N) {
// предварительно считаем логарифмы
lg[1] = 0;
for (int i = 2; i <= N; i++) {
lg[i] = lg[i / 2] + 1;
}
// инициализация для длины 1
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] = 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 обычно достаточно в большинстве задач
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]);
}