Отложенные операции
Очень часто при решении задач на дерево отрезков, декартово дерево, корневую декомпозицию требуется применять операцию изменения не к одному элементу массива, а к подотрезку.
Замечание. Считается, что мы умеем применять эту операцию к одному элементу массива, и что мы умеем применять ее «по частям» (к разным подотрезкам массива по очереди).
Применим следующий трюк: если нам нужно обновить значение подотрезка, то мы отложим эту операцию до востребования. Запомним в соответствующих вершине/блоке, что мы должны в будущем сделать обновление в потомков. Если нам вдруг понадобится значение, лежащее в вершине/блоке, то мы посчитаем его так, как будто мы обновили отрезок, а напоминание о том, что надо сделать со всеми элементами, мы «протолкнем» в потомков (отсюда и название push).
Приведем тут несколько мыслей и реализацию для дерева отрезков.
- Вызывать push надо каждый раз, когда мы обращаемся к вершине, если между обращениями к ней могло примениться обновление
- push-пометки надо не забывать очищать
- если мы снимаем push-пометку с единичного элемента, то мы про нее можем забыть
В данной реализации мы делаем присвоение на отрезке и получение значения в точке.
1 struct segtree 2 int val = 0; 3 int push = -1; 4 >; 5 6 segtree t[4 * MAXN]; 7 8 void push(int v, int tl, int tr) 9 if (t[v].push == -1) 10 return; 11 > 12 if (tl + 1 == tr) 13 t[v].val = t[v].push; 14 > 15 else 16 t[2 * v].push = t[v].push; 17 t[2 * v + 1].push = t[v].push; 18 > 19 t[v].push = -1; 20 > 21 22 inline void upd(int v, int tl, int tr, int l, int r, int x) 23 push(v, tl, tr); 24 if (tl >= r || l >= tr) 25 return; 26 > 27 if (l tl && tr r) 28 t[v].push = x; 29 push(v, tl, tr); 30 return; 31 > 32 int tm = (tl + tr) / 2; 33 upd(2 * v, tl, tm, l, r, x); 34 upd(2 * v + 1, tm, tr, l, r, x); 35 > 36 37 inline int get(int v, int tl, int tr, int pos) 38 push(v, tl, tr); 39 if (tl + 1 == tr) 40 return t[v].val; 41 > 42 int tm = (tl + tr) / 2; 43 if (pos tm) 44 return get(2 * v, tl, tm, pos); 45 > 46 else 47 return get(2 * v + 1, tm, tr, pos); 48 > 49 >
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s
Источник
Отложенное построение
Рассмотрим нашу любимую задачу суммы на подотрезках, но теперь все индексы лежат не в пределах $10^5$ или $10^6$, а до $10^9$ или даже $10^$.
Все асимптотики нас по прежнему более-менее устраивают:
$$ \log_2 10^6 \approx 20 \\ \log_2 10^9 \approx 30 \\ \log_2 10^ \approx 60 $$
Единственная проблема — это этап построения, работающий за линейное от $n$ время и память.
Решить её можно отказавшись от явного создания всех вершин дерева в самом начале. Изначально создадим только лишь корень, а остальные вершины будем создавать на ходу, когда в них потребуется записать что-то не дефолтное — как в lazy propagation:
Теперь по аналогии с push будем в начале всех методов будем проверять, что дети-вершины созданы, и создавать их, если это не так.
Такой метод в основном приеним только к реализации на указателях, однако при использовании индексаций можно хранить вершины не в массиве, а в хеш-таблице: запросы станут работать дольше, но не асимптотически. Отметим также, что в любом случае на каждый запрос потребуется $O(\log n)$ дополнительной памяти для создания новых вершин, что обычно приводит к асимптотике $O(q \log n)$ по памяти.
Также, если все запросы известны заранее, то их координаты можно просто сжать перед обработкой запросов. Автор обычно делает это так:
В большинстве случаев, использовать динамическое построение — это как стрелять из пушки по воробьям. Попробуйте сначала более простые методы: возможно, всё просто в set влезает.
Источник
Дерево отрезков
Нам дан массив $a_0,\ a_1,\ \ldots,\ a_$. Требуется обрабатывать два типа запросов:
Мы хотим, чтобы каждый запрос обрабатывался за $O(\log n)$.
Замечание. Если запросов обновления нет, то данная задача решается с помощью префиксных сумм.
Нам понадобится хранить сумму на некоторых подотрезках, а потом склеивать их при ответе на запрос. Сделаем с исходным массивом следующие манипуляции:
- Посчитаем сумму всего массива и где-нибудь запишем.
- Разделим его пополам, посчитаем сумму на половинах и тоже где-нибудь запишем.
- Каждую половину потом разделим пополам ещё раз, и так далее, пока не придём к отрезкам длины 1.
Такое дерево имеет высоту $O(\log n)$, при этом каждая его вершина хранит сумму на каком-то подотрезке массива. Ровно эту структуру данных мы и будем называть деревом отрезков.
Утверждение:
Вершин в дереве $O(n)$
Доказательство:
Если разбить дерево на «слои», то в них будет $$1\ +\ 2\ +\ 4\ +\ \ldots\ + 2^$$ вершин суммарно (если мы обозначили высоту дерева за $h$), что равно $O(2^h)$. При $h\ =\ O(\log n):\ O(2^h)\ =\ O(n)$.
Мы еще не сказали, как быстро посчитать значения сумм для всех вершин. Строить будем такой рекурсивной процедурой:
- Смотрим на текущие параметры $[l,\ r)$ вершины (иначе говоря, границы ее отрезка).
- Если $r\ -\ l\ =\ 1$, то вершина отвечает ровно за 1 элемент, и сумма считается тривиально.
- Иначе мы разбиваем отрезок на два: $m\ := \lfloor\frac\rfloor;\ [l,\ r)\ \rightarrow\ [l,\ m),\ [m,\ r)$. Выполним процедуру рекурсивно для новых отрезков (назвав новые две вершины детьми текущей, а потом сохраним $sum_<[l,\ r)>\ =\ sum_<[l,\ m)>\ +\ sum_<[m,\ r)>$ в своей вершине.
Сохранять все вершины будем в массив, поддерживая такую нумерацию:
- Если вершина — корень, то у нее номер 1.
- Если у вершины с номером $v$ есть левый и правый ребенок, то их номера — $2 \cdot v$ и $2 \cdot v + 1$.
Проведем следующую операцию:
- Запомним параметры $[l_q,\ r_q)$ запроса.
- Посмотрим на текущую вершину (изначально — корень дерева). Если ее отрезок не пересекается с отрезком запроса, то все вершины в ее поддереве нам тоже неинтересны, поэтому можно не рассматривать эту вершину.
- Если отрезок нашей вершины вложен в отрезок запроса, то мы можем прибавить посчитанное в вершине значение суммы к ответу.
- Если отрезок нашей вершины пересекается с отрезком запроса, то рекурсивно проведем операцию в наших потомках.
Очевидно, что таким образом мы действительно посчитаем сумму на всем отрезке.
Утверждение:
Данная процедура работает за $O(\log n)$
Доказательство:
Посмотрим на самую левую и самую правую вершины, посчитанные при ответе на запрос. Все вершины, лежащие между ними, были рассмотрены за $O(1)$, потому что лежали внутри запроса. Аналогично за $O(1)$ была рассмотрена каждая вершина вне отрезка. За время спуска к двум крайним вершинам процедура рассмотрела $O(\log n)$ вершин, которые были обработаны за $O(1)$.
Для обновления одного элемента надо спуститься к нему по дереву, изменить значение в листе, а потом заново пересчитать все значения в вершинах на пути до корня. Аналогично, это работает за $O(\log n)$.
1 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] = 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] = t[2 * v] + t[2 * v + 1]; 13 > 14 15 void upd(int v, int l, int r, int pos, int x) 16 if (l + 1 == r) 17 t[v] = x; 18 return; 19 > 20 int m = (l + r) / 2; 21 if (pos m) 22 upd(2 * v, l, m, pos, x); 23 > 24 else 25 upd(2 * v + 1, m, r, pos, x); 26 > 27 t[v] = t[2 * v] + t[2 * v + 1]; 28 > 29 30 int get(int v, int l, int r, int ql, int qr) 31 if (ql >= r || l >= qr) 32 return NEUTRAL; 33 > 34 if (ql l && qr r) 35 return t[v]; 36 > 37 int m = (l + r) / 2; 38 return get(2 * v, l, m, ql, qr) + get(2 * v + 1, m, r, ql, qr)); 39 >
Мы уже решили исходную задачу, поэтому давайте просто дополним статью еще несколькими трюками. Если в задаче нам требуется делать какую-то операцию на отрезке (например, присвоить всем элементам значение $x$), то мы будем находить соответствующие запросу изменения вершины, и в них пользоваться техникой отложенных операций.
Автор конспекта: Константин Амеличев
По всем вопросам пишите в telegram @kik0s
Источник