Merge sort tree: различия между версиями
KiKoS (обсуждение | вклад) (Новая страница: «====Задача==== Дан массив $a_0,\ \ldots,\ a_{n-1}$. Требуется ответить на $q$ запросов: * $?\ l,\ r,\ x$ — колич...») |
KiKoS (обсуждение | вклад) м (code + category) |
||
Строка 9: | Строка 9: | ||
Каждый элемент массива будет храниться в $O(\log n)$ массивах — на пути от листа до корня, поэтому наша структура будет занимать $O(n \log n)$ памяти. Построение работает за $O(n \log n)$ (см. [Сортировка слиянием#Асимптотика]), а ответ на запрос за $O(\log^2 n)$. | Каждый элемент массива будет храниться в $O(\log n)$ массивах — на пути от листа до корня, поэтому наша структура будет занимать $O(n \log n)$ памяти. Построение работает за $O(n \log n)$ (см. [Сортировка слиянием#Асимптотика]), а ответ на запрос за $O(\log^2 n)$. | ||
− | + | <syntaxhighlight lang='c++' line='line'> | |
+ | struct segtree { | ||
+ | vector<int> val; | ||
+ | }; | ||
+ | |||
+ | segtree t[4 * MAXN]; | ||
+ | |||
+ | void build(int v, int tl, int tr) { | ||
+ | if (tl + 1 == tr) { | ||
+ | t[v].val.push_back(a[tl]); | ||
+ | return; | ||
+ | } | ||
+ | int tm = (tl + tr) / 2; | ||
+ | build(2 * v, tl, tm); | ||
+ | build(2 * v + 1, tm, tr); | ||
+ | t[v].val.resize(t[2 * v].val.size() + t[2 * v + 1].val.size()); | ||
+ | merge(t[2 * v].val.begin(), t[2 * v].val.end(), | ||
+ | t[2 * v + 1].val.begin(), t[2 * v + 1].val.end(), | ||
+ | t[v].val.begin()); | ||
+ | } | ||
+ | |||
+ | int get(int v, int tl, int tr, int l, int r, int x) { | ||
+ | if (tl >= r || l >= tr) { | ||
+ | return 0; | ||
+ | } | ||
+ | if (l <= tl && tr <= r) { | ||
+ | return lower_bound(t[v].val.begin(), t[v].val.end(), x - 1) - t[v].val.begin(); | ||
+ | } | ||
+ | int tm = (tl + tr) / 2; | ||
+ | return get(2 * v, tl, tm, l, r, x) + get(2 * v + 1, tm, tr, l, r. x); | ||
+ | } | ||
+ | </syntaxhighlight> | ||
Версия данной задачи с запросами изменения потребует [[Двухмерные структуры данных|более тяжелых структур]]. | Версия данной задачи с запросами изменения потребует [[Двухмерные структуры данных|более тяжелых структур]]. | ||
Строка 15: | Строка 46: | ||
{{Автор|Константин Амеличев|kik0s}} | {{Автор|Константин Амеличев|kik0s}} | ||
+ | [[Категория:Структуры данных для запросов на отрезке]] |
Версия 17:33, 18 сентября 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