Бардоштҳои дуӣ (ҷаҳишҳо)
Бардоштҳои дуӣ (ҷаҳишҳо)
Муқаддима
Соддатарин масъала барои бардоштҳои дуӣ чунин садо медиҳад: Дарахти вазндори бо қулла дода шудааст. Лозим аст ба дархостҳои намуди - ёфтани аҷдоди -уми қуллаи ҷавоб диҳем.
Бардоштҳои дуӣ (ҷаҳишҳо)
Соддатарин масъала барои бардоштҳои дуӣ чунин садо медиҳад: Дарахти вазндори бо қулла дода шудааст. Лозим аст ба дархостҳои намуди - ёфтани аҷдоди -уми қуллаи ҷавоб диҳем.
-ро аҷдоди қуллаи меномем. Он гоҳ барои ёфтани аҷдоди -уми қуллаи бояд маротиба кунем.
Ин ҳал суст кор мекунад, яъне бо .
Вақте ки мо аз як қулла ба аҷдод боло меравем, биёед инро ҷаҳиш номем. Дар ҳалли боло мо ҷаҳишҳои дарозии мекардем (яъне ба аҷдод боло мешудем).
Идеяи бардоштҳои дуӣ дар он аст, ки ҷаҳишҳоро на танҳо бо дарозии , балки бо дарозии барои ҳар гуна анҷом диҳем. Аз ҳамин ҷо номи ин техника ҳам омадааст.
Бигзор маънои аҷдоди -уми қуллаи -ро дошта бошад. Мо дорем:
Ҳамин тавр метавон маротиба аз қуллаи бо боло рафт. Зеро -ро метавон дар шакли на бештар аз дараҷаҳои ду ифода кард. Масалан, барои метавон ҳамагӣ маротиба бо дарозиҳои ҷаҳид.
Асимптотика мешавад.
Ҳамчунин намудҳои гуногуни дигар масъалаҳо ҳастанд, ки дар онҳо низ лозим аст самаранок тавонистан аз як нуқта ба нуқтаи дигар ҷаҳидан. Масалан, идеяи Sparse Table-ро ҳам метавон дар ҳамин шакл тасаввур кард.
Массиви аз адад дода шудааст. Лозим аст дархостҳои намуди: ёфтани минимум дар порчаи -ро коркард кунем.
Биёед шартро каме аз нав баён кунем. Сангпушт дар мавқеи қарор дорад ва ба рост маротиба ҳаракат мекунад. Кадом адади минималиро ӯ дар роҳ вомехӯрад? Биёед инро get_min номем.
Бигзор адади минималие бошад, ки сангпушт дар роҳи худ, аз мавқеи оғоз карда, ба рост маротиба рафта ва худи мавқеи -ро дохил накарда, вомехӯрад. Он гоҳ дорем:
Ва ҷавоб барои порчаи get_min хоҳад буд
int find_par(int x, int k) {
for (int i = 0; i < k; i++) {
x = par[x];
}
return x;
}
const int L = 20; // log(N)
void init() {
for (int i = 1; i <= n; i++) {
par[i][0] = p[i]; // p[i] is parent of vertex i
}
for (int i = 1; i < L; i++) {
for (int j = 1; j <= n; j++) {
par[j][i] = par[par[j][i - 1]][i - 1];
}
}
}
int get_par(int x, int k) {
for (int i = 0; i < L; i++) {
if (k & (1 << i)) {
x = par[x][i];
}
}
return x;
}
const int L = 20; // log(N)
void init() {
for (int i = 1; i < n; i++) {
f[i][0] = A[i + 1];
}
for (int i = 1; i < L; i++) {
for (int j = 1; j + (1 << i) <= n; j++) {
f[j][i] = min(f[j][i - 1], f[j + (1 << i - 1)][i - 1]);
}
}
}
int get_min(int x, int k) {
int res = A[x];
for (int i = 0; i < L; i++) {
if (k & (1 << i)) {
res = min(res, f[x][i]); // update answer
x += (1 << i); // jump with length 2^i
}
}
return res;
}