Merge sort tree

Содержание

1 Задача
2 Решение
3 Построение
4 Время работы и используемая память

Задача

Дан массив $a_0,\ \ldots,\ a_{n-1}$. Требуется ответить на $q$ запросов:

$?\ l,\ r,\ x$ — количество элементов на $a_l,\ \ldots,\ a_r$, меньших $x$.

Решение

Если подотрезок массива отсортирован, то мы умеем отвечать на такой запрос за $O(\log n)$ с помощью бинпоиска. Построим дерево отрезков на нашем массиве, а в каждой вершине будем хранить отсортированную версию соответствующего подотрезка массива. Тогда ответ на запрос работает за $O(\log^2 n)$ — мы делаем обычный get-запрос в дереве отрезков, отличающийся лишь получением ответа на подотрезке, потому что там мы будем делть бинпоиск.

Построение

Для того, чтобы быстро построить merge sort tree, воспользуемся идеей merge sort'а (собственно, отсюда и название). Для каждой вершины будем хранить копию ее подотрезка (о затратах на память поговорим позже). Если вершина отвечает за отрезок длины 1, то ее массив уже отсортирован. А если у сыновей вершиины отсортированы массивы, то мы их можем просто слить за линейное время.

Время работы и используемая память

Каждый элемент массива будет храниться в $O(\log n)$ массивах — на пути от листа до корня, поэтому наша структура будет занимать $O(n \log n)$ памяти. Построение работает за $O(n \log n)$ (см. тут), а ответ на запрос за $O(\log^2 n)$.

 1 struct segtree {
 2 	vector<int> val;
 3 };
 4 
 5 segtree t[4 * MAXN];
 6 
 7 void build(int v, int tl, int tr) {
 8 	if (tl + 1 == tr) {
 9 		t[v].val.push_back(a[tl]);
10 		return;
11 	}
12 	int tm = (tl + tr) / 2;
13 	build(2 * v, tl, tm);
14 	build(2 * v + 1, tm, tr);
15 	t[v].val.resize(t[2 * v].val.size() + t[2 * v + 1].val.size());
16 	merge(t[2 * v].val.begin(), t[2 * v].val.end(),
17               t[2 * v + 1].val.begin(), t[2 * v + 1].val.end(),
18               t[v].val.begin());
19 }
20 
21 int get(int v, int tl, int tr, int l, int r, int x) {
22 	if (tl >= r || l >= tr) {
23 		return 0;
24 	}
25 	if (l <= tl && tr <= r) {
26 		return lower_bound(t[v].val.begin(), t[v].val.end(), x - 1) - t[v].val.begin();
27 	}
28 	int tm = (tl + tr) / 2;
29 	return get(2 * v, tl, tm, l, r, x) + get(2 * v + 1, tm, tr, l, r, x);
30 }

Версия данной задачи с запросами изменения потребует более тяжелых структур.

Автор конспекта: Константин Амеличев

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