А что еще можно хранить в до?

Задача

А подходит ли Дерево отрезков для каких-то более интересных запросов? Давайте решать следующую задачу :

Дан массив $a$ длины $n$, поступают запросы двух видов :

1) Найти количество чисел $\le x$ на отрезке с $l$ по $r$.

Идея

Давайте хранить внутри каждой вершины дерева отрезков отсортированный массив, построить такое до несложно, например можно это сделать как в merge-sort, рекурсивно сортируя массив в левой половине и правой половине, а затем делая merge двух массив.

 1 vector<int> t[MAXN * 4];
 2 int a[MAXN];
 3 
 4 void build(int v, int l, int r) {
 5 	if (l + 1 == r) {
 6 		t[v].push_back(a[l]);
 7 		return;
 8 	}
 9 	int m = (l + r) / 2;
10 	build(2 * v, l, m);
11 	build(2 * v + 1, m, r);
12 	t[v] = merge(t[2 * v], t[2 * v + 1]);
13 }

Тогда ответ на запрос - просто в каждой вершине отрезка сделаем бинпоиск по значению $x$ и сложим значения на всех вершинах до внутри отрезка :

 1 int get(int v, int l, int r, int ql, int qr, int x) {
 2 	if (ql >= r || l >= qr) {
 3 		return 0;
 4 	}
 5 	if (ql <= l && qr <= r) {
 6 		return upper_bound(t[v].begin(), t[v].end(), x) - t[v].begin();
 7 	}
 8 	int m = (l + r) / 2;
 9 	return get(2 * v, l, m, ql, qr, x) + get(2 * v + 1, m, r, ql, qr, x));
10 }

Асимптотика

Каждый элемент встречается в $O(h)$ количестве вершин дерева отрезков, то есть по памяти наше решение работает за $O(n \log(n))$, по времени оно работает за $O(m \log^2(n))$, так как в каждой вершине до мы делаем бинпоиск за $O(\log(n))$, в каждом запросе мы посещаем $\log(n)$ вершин ДО.

Дополнительно

К данной идеи можно применить и запросы изменения в точке, более того можно решать класс более сложных задач : Например запрос медианы отрезка.

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin