Альтернативная реализация Дерева Отрезков с отложенными операциями

Материал из Algocode wiki
Перейти к: навигация, поиск
 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 using ll = long long;
 5 
 6 const int INF = 1e9 + 5;
 7 const int MAXN = 1e5 + 5;
 8 
 9 struct node {
10     ll min; // минимум в вершине БЕЗ учета отложенной операции
11     ll add; // отложенная операция (сколько нужно прибавить на отрезке)
12 };
13 
14 // 0 - корень, левый сын - v * 2 + 1, правый - v * 2 + 2
15 node t[MAXN * 4];
16 
17 // получает значение в вершине v с учетом отложенной операции
18 ll get(int v) {
19     return t[v].min + t[v].add;
20 }
21 
22 // "проталкивает" отложенную операцию в детей и обновляет минимум в вершине
23 void push(int v) {
24     // так как прибавить 0 = ничего не делать, то тут можно не писать дополнительную проверку на то,
25     // что отложенной операции нет, но надо иметь в виду, что в некоторых задачах такая проверка необходима
26 
27     // Минимум в вершине, увеличится ровно на то, что нужно прибавить
28     // (так как прибавляем ко всем числам на отрезке)
29     t[v].min += t[v].add;
30 
31     // В детях это изменение еще не учтено, пропушим его в них
32     t[v * 2 + 1].add += t[v].add;
33     t[v * 2 + 2].add += t[v].add;
34 
35     // После применения отложенной операции, занулим t[v].add, чтобы позже не прибавить еще раз
36     t[v].add = 0;
37 }
38 
39 // Прибавить x на отрезке
40 // v - вершина 
41 // [tl, tr) - отрезок вершины ДО (правая граница не включается)
42 // [l, r) - отрезок запроса (правая граница не включается)
43 // x - то, что хотим прибавить на отрезке
44 void update(int v, int tl, int tr, int l, int r, int x) {
45     // вершина дерева вообще не попадает в отрезок запроса, ничего не делаем
46     if (r <= tl || tr <= l) return;
47 
48     // вершина дерева полностью попадает в отрезок запроса
49     if (l <= tl && tr <= r) {
50         // скажем, что когда-нибудь потом в этой вершине нужно будет прибавить x
51         t[v].add += x;
52         return;
53     }
54 
55     // если мы попали сюда, значит вершина дерева пересекается с отрезком запроса, и нужно спускаться в детей.
56     // но возможно, в текущей вершине есть отложенная операция, которую нужно применить к детям, поэтому вызовем push
57     push(v);
58 
59     // спускаемся в детей
60     int tm = tl + (tr - tl) / 2;
61     update(v * 2 + 1, tl, tm, l, r, x);
62     update(v * 2 + 2, tm, tr, l, r, x);
63 
64     // в нашей вершине точно нет отложенной операции, потому что выше вызвали push, поэтому можно просто
65     // пересчитать min из детей. Так как в детях могут быть отложенные операции, то получим значения в них, используя get
66     t[v].min = min(get(v * 2 + 1), get(v * 2 + 2));
67 }
68 
69 // Получить минимум на отрезке
70 // v - вершина
71 // [tl, tr) - отрезок вершины ДО (правая граница не включается)
72 // [l, r) - отрезок запроса (правая граница не включается)
73 ll get(int v, int tl, int tr, int l, int r) {
74     // вершина дерева вообще не попадает в отрезок запроса, ничего не делаем
75     if (r <= tl || tr <= l) {
76         return INF;
77     }
78 
79     // вершина дерева полностью попадает в отрезок запроса
80     if (l <= tl && tr <= r) {
81         // вернем минимум с учетом отложенной операции
82         return get(v);
83     }
84 
85     // если мы попали сюда, значит вершина дерева пересекается с отрезком запроса, и нужно спускаться в детей.
86     // но возможно, в текущей вершине есть отложенная операция, которую нужно применить к детям, поэтому вызовем push
87     push(v);
88 
89     // получаем ответы из детей и берем минимум из них
90     int tm = tl + (tr - tl) / 2;
91     ll a = get(v * 2 + 1, tl, tm, l, r);
92     ll b = get(v * 2 + 2, tm, tr, l, r);
93     return min(a, b);
94 }



Автор конспекта: Андрей Одинцов

По всем вопросам пишите в telegram @forestryks