Merge sort tree: различия между версиями
KiKoS (обсуждение | вклад) м |
KiKoS (обсуждение | вклад) м |
||
Строка 46: | Строка 46: | ||
{{Автор|Константин Амеличев|kik0s}} | {{Автор|Константин Амеличев|kik0s}} | ||
+ | [[Категория:Конспект]] | ||
[[Категория:Структуры данных для запросов на отрезке]] | [[Категория:Структуры данных для запросов на отрезке]] |
Версия 13:22, 27 сентября 2019
Задача
Дан массив $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