Отложенные операции: различия между версиями
KiKoS (обсуждение | вклад) (Новая страница: «Очень часто при решении задач на [дерево отрезков], [декартово дерево], Корневая декомпо...») |
KiKoS (обсуждение | вклад) м (code + category) |
||
Строка 9: | Строка 9: | ||
* если мы снимаем push-пометку с единичного элемента, то мы про нее можем забыть | * если мы снимаем push-пометку с единичного элемента, то мы про нее можем забыть | ||
− | + | В данной реализации мы делаем присвоение на отрезке и получение значения в точке. | |
+ | <syntaxhighlight lang='c++' line='line'> | ||
+ | struct segtree { | ||
+ | int val = 0; | ||
+ | int push = -1; | ||
+ | }; | ||
+ | |||
+ | segtree t[4 * MAXN]; | ||
+ | |||
+ | void push(int v, int tl, int tr) { | ||
+ | if (t[v].push == -1) { | ||
+ | return; | ||
+ | } | ||
+ | if (tl + 1 == tr) { | ||
+ | t[v].val = t[v].push; | ||
+ | } | ||
+ | else { | ||
+ | t[2 * v].push = t[v].push; | ||
+ | t[2 * v + 1].push = t[v].push; | ||
+ | } | ||
+ | t[v].push = -1; | ||
+ | } | ||
+ | |||
+ | inline void upd(int v, int tl, int tr, int l, int r, int x) { | ||
+ | push(v, tl, tr); | ||
+ | if (tl >= r || l >= tr) { | ||
+ | return; | ||
+ | } | ||
+ | if (l <= tl && tr <= r) { | ||
+ | t[v].push = x; | ||
+ | push(v, tl, tr); | ||
+ | return; | ||
+ | } | ||
+ | int tm = (tl + tr) / 2; | ||
+ | upd(2 * v, tl, tm, l, r, x); | ||
+ | upd(2 * v + 1, tm, tr, l, r, x); | ||
+ | } | ||
+ | |||
+ | inline int get(int v, int tl, int tr, int pos) { | ||
+ | push(v, tl, tr); | ||
+ | if (tl + 1 == tr) { | ||
+ | return t[v].val; | ||
+ | } | ||
+ | int tm = (tl + tr) / 2; | ||
+ | if (pos <= tm) { | ||
+ | return get(2 * v, tl, tm, pos); | ||
+ | } | ||
+ | else { | ||
+ | return get(2 * v + 1, tm, tr, pos); | ||
+ | } | ||
+ | } | ||
+ | </syntaxhighlight> | ||
{{Автор|Константин Амеличев|kik0s}} | {{Автор|Константин Амеличев|kik0s}} | ||
+ | [Категория:Структуры данных для запросов на отрезке] |
Версия 17:40, 18 сентября 2019
Очень часто при решении задач на [дерево отрезков], [декартово дерево], корневую декомпозицию требуется применять операцию изменения не к одному элементу массива, а к подотрезку. Замечание. Считается, что мы умеем применять эту операцию к одному элементу массива, и что мы умеем применять ее "по частям" (к разным подотрезкам массива по очереди).
Push-величины
Применим следующий трюк: если нам нужно обновить значение подотрезка, то мы отложим эту операцию до востребования. Запомним в соответствующих вершине/блоке, что мы должны в будущем сделать обновление в потомков. Если нам вдруг понадобится значение, лежащее в вершине/блоке, то мы посчитаем его так, как будто мы обновили отрезок, а напоминание о том, что надо сделать со всеми элементами, мы "протолкнем" в потомков (отсюда и название 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 [Категория:Структуры данных для запросов на отрезке]