Отложенные операции

Материал из Algocode wiki
Перейти к: навигация, поиск

Очень часто при решении задач на дерево отрезков, декартово дерево, корневую декомпозицию требуется применять операцию изменения не к одному элементу массива, а к подотрезку.

Замечание. Считается, что мы умеем применять эту операцию к одному элементу массива, и что мы умеем применять ее "по частям" (к разным подотрезкам массива по очереди).

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