Ikkilik ko‘tarilishlar (sakrashlar)
Ikkilik ko‘tarilishlar uchun eng bazaviy vazifa shunday: ta cho‘qqiga ega og‘irlikli daraxt berilgan. ta so‘rovga javob berish talab qilinadi: cho‘qqining -chi ajdodini topish.
cho‘qqining ajdodini deb belgilaymiz. Unda cho‘qqining -chi ajdodini topish uchun marta qilish kerak.
Ushbu yechim sekin ishlaydi, ya’ni .
Bir cho‘qqidan ajdodga ko‘tarilayotganimizda, buni sakrash deb ataylik. Yuqoridagi yechimda biz uzunligi bo‘lgan sakrashlar qilgan edik (ya’ni ajdodga ko‘tarilardik).
Ikkilik ko‘tarilishlar g‘oyasi shundan iboratki, nafaqat uzunligi , balki istalgan uchun uzunligi bo‘lgan sakrashlarni ham qilish. Shu yerdan ushbu texnikaning nomi kelib chiqqan.
cho‘qqining -chi ajdodini anglatadi. Bizda:
Shunday qilib, cho‘qqidan marta ko‘tarilishni da bajarish mumkin. Chunki ni ko‘pi bilan ta ikkilik darajalar yig‘indisi ko‘rinishida ifodalash mumkin. Masalan, uchun atigi marta uzunliklarda sakrash mumkin.
Asimptotika bo‘ladi.
Yana turli boshqa turdagi masalalar ham bo‘ladi, ularda ham bir nuqtadan boshqasiga samarali sakray olish kerak. Masalan, Sparse Table g‘oyasini ham shu ko‘rinishda tasavvur qilish mumkin.
ta sondan iborat massivi berilgan. ta so‘rovni qayta ishlash talab qilinadi: kesmada minimumni topish.
Keling, masala shartini biroz qayta ifodalaymiz. Toshbaqa pozitsiyada turibdi va o‘ngga marta harakat qiladi. Yo‘lda u uchratadigan eng kichik son qaysi? Buni get_min deb ataylik.
toshbaqa pozitsiyadan boshlab o‘ngga marta yurib, pozitsiyaning o‘zini kiritmagan holda yo‘lida uchratadigan eng kichik son bo‘lsin. Unda:
kesma uchun javob esa get_min bo‘ladi
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;
}