Спуск по дереву отрезков
Содержание
Задача
Для данных $l_i$ и $x_i$ найти наименьшее $r_i$, такое что $l_i \le r_i$ и $x_i < a[r_i]$ - близайшее большее справа.
Простое решение за O(nlog^2)
Заведем ДО на максимум и найдем ответ бинарным поиском. В бинпоиске нам нужно уметь отвечать на запрос, есть ли на отрезке $[l \ldots m]$ число больше x - это легко проверить, найдя максимум на отрезке $[l \ldots m]$.
Идея
В бинарном поиске мы делим отрезок пополам и что-то проверяем, но Дерево Отрезков тоже делит отрезки пополам и что-то про них знает, нельзя ли этим воспользоваться? - попробуем
Если для всех запросов $l = 0$, то идея довольно проста, напишем код, который используя значения в вершинах ДО будет делать то же, что дулал бы бинпоиск:
int find(int v, int tl, int tr, int x) {
if (tl + 1 == tr) { // дошли до листовой вершины
if (tree[v] > x) {
return tl; // вершина подходит
} else {
return -1; // ответа нет во всем дереве
}
}
int tm = (tl + tr) / 2;
int left_son = 2 * v + 1; // или другая формула, если вы не в 0-нумерации
int right_son = 2 * v + 2;
if (tree[left_son] > x) return find(left_son, tl, tm, x); // если ответ слева есть, найдем его там
return find(right_son, tm, tr, x);
}
Решение
Если $l \neq 0$ придется вспомнить, что суффикс $[l \cdots n] $ в дереве отрезков разбит на O(log) отрезков. Первым делом найдем тот из них, в который нужно спуститься, а затем вызовем find.
int find_segment(int v, int tl, int tr, int l, int x) { // возвращает итоговый ответ на запрос
if (tr <= l) return -1;
if (l <= tl) {
if (tree[v] > x) return find(v, tl, tr, x); // если можем найти ответ в этом отрезке
return -1;
}
int tm = (tl + tr) / 2;
int left_son = 2 * v + 1; // или другая формула, если вы не в 0-нумерации
int right_son = 2 * v + 2;
int left_ans = find_segment(left_son, tl, tm, l, x);
if (left_ans != -1) return left_ans;
return find_segment(right_son, tm, tr, l, x);
}
Эта реализация сначала разобьет суффикс на O(log) отрезков, потом найдет тот, в который спуститься и ещё за O(log) спустится и найдет ответ.
Итого O(log(n)) на запрос.
Автор конспекта: Евтеев Тихон
По всем вопросам пишите в telegram @tikhon282