Двоичные подъёмы (прыжки)
Двоичные подъёмы (прыжки)
Введение
Самая базовая задача для двоичных подъемов звучит так: Дано взвешенное дерево с вершинами. Требуется ответить на запросов вида - найти -ый предок вершины .
Двоичные подъёмы (прыжки)
Самая базовая задача для двоичных подъемов звучит так: Дано взвешенное дерево с вершинами. Требуется ответить на запросов вида - найти -ый предок вершины .
Обозначим за предок вершины . Тогда для нахождения -ого предка вершины надо раз сделать .
Данное решение работает медленно, а именно за .
Когда мы поднимаемся из одной вершины к предку, то давайте назовем это прыжком. В вышесказанном решении мы делали прыжки длиной (т.е. поднимались к предку).
Идея бинарных подъемов заключается в том, чтобы делать прыжки не только длиной , но и длиной для любого . Отсюда и название данной техники.
Пусть будет означать -ый предок вершины . Мы имеем:
Таким образом можно подниматься раз с вершины за . Т.к. можно представить в виде не более степеней двойки. Например, для можно прыгать всего раза длинами .
Асимптотика будет .
Бывают еще различные другие тип задач где также нужно эффективно уметь прыгать из одной точки до другой. Например, идею 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;
}