Спуск по дереву отрезков

Задача

Для данных $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