Отложенные операции
Очень часто при решении задач на дерево отрезков, декартово дерево, корневую декомпозицию требуется применять операцию изменения не к одному элементу массива, а к подотрезку. Замечание. Считается, что мы умеем применять эту операцию к одному элементу массива, и что мы умеем применять ее "по частям" (к разным подотрезкам массива по очереди).
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 [Категория:Структуры данных для запросов на отрезке]