Спуск по дереву отрезков: найти первый элемент >= x за O(log n), а не O(log^2 n)?
Есть дерево отрезков на максимум. Хочу для запроса найти первую позицию p (самую левую), где a[p] >= x. Можно было бы делать бинпоиск + query за O(log^2 n), но слышал, что есть спуск за один O(log n). Как он устроен?
2 ответа
Спуск по дереву (descent) — идём от корня, на каждом узле решаем, в какого ребёнка пойти, не делая отдельных запросов. Дерево на максимум: в узле хранится максимум поддерева. Если максимум поддерева < x, там подходящего элемента нет — отсекаем.
// первая позиция в [l, n-1] с a[pos] >= x, или -1
int t[4*N]; // максимум
int firstGE(int v, int tl, int tr, int l, int x) {
if (tr < l || t[v] < x) return -1; // нет шансов
if (tl == tr) return tl; // лист подходит
int tm = (tl + tr) / 2;
int res = firstGE(2*v, tl, tm, l, x); // сначала левее
if (res != -1) return res;
return firstGE(2*v+1, tm+1, tr, l, x);
}
Почему это O(log n), хотя выглядит как обычный обход? Из-за отсечения t[v] < x и tr < l мы спускаемся вглубь только вдоль одной «активной» ветки — суммарно посещаем O(log n) узлов плюс O(log n) узлов на границе диапазона. В отличие от O(log^2 n) бинпоиска тут один проход.
Для запроса с правой границей добавьте проверку tl > r тоже, либо ограничьте [l, r] явно в условиях отсечения.
Если левой границы нет (ищем по всему массиву, l = 0), спуск ещё короче — он строго идёт по одному пути:
int firstGE_full(int x) {
if (t[1] < x) return -1;
int v = 1, tl = 0, tr = n - 1;
while (tl < tr) {
int tm = (tl + tr) / 2;
if (t[2*v] >= x) { v = 2*v; tr = tm; } // есть слева
else { v = 2*v+1; tl = tm+1; } // иначе справа
}
return tl;
}
Это гарантированно O(log n) без рекурсии. Такой паттерн обобщается: «найти k-ю единицу», «найти позицию по префиксной сумме» — везде на каждом шаге смотрим на левого ребёнка и решаем, хватает ли его, чтобы свернуть влево, иначе вычитаем его вклад и идём вправо.