Альтернативная реализация Дерева Отрезков с отложенными операциями: различия между версиями
Материал из Algocode wiki
(Новая страница: «<syntaxhighlight lang='c++' line='line'> </syntaxhighlight>») |
|||
Строка 1: | Строка 1: | ||
<syntaxhighlight lang='c++' line='line'> | <syntaxhighlight lang='c++' line='line'> | ||
+ | #include <bits/stdc++.h> | ||
+ | using namespace std; | ||
+ | using ll = long long; | ||
+ | |||
+ | const int INF = 1e9 + 5; | ||
+ | const int MAXN = 1e5 + 5; | ||
+ | |||
+ | struct node { | ||
+ | ll min; // минимум в вершине БЕЗ учета отложенной операции | ||
+ | ll add; // отложенная операция (сколько нужно прибавить на отрезке) | ||
+ | }; | ||
+ | |||
+ | // 0 - корень, левый сын - v * 2 + 1, правый - v * 2 + 2 | ||
+ | node t[MAXN * 4]; | ||
+ | |||
+ | // получает значение в вершине v с учетом отложенной операции | ||
+ | ll get(int v) { | ||
+ | return t[v].min + t[v].add; | ||
+ | } | ||
+ | |||
+ | // "проталкивает" отложенную операцию в детей и обновляет минимум в вершине | ||
+ | void push(int v) { | ||
+ | // так как прибавить 0 = ничего не делать, то тут можно не писать дополнительную проверку на то, | ||
+ | // что отложенной операции нет, но надо иметь в виду, что в некоторых задачах такая проверка необходима | ||
+ | |||
+ | // Минимум в вершине, увеличится ровно на то, что нужно прибавить | ||
+ | // (так как прибавляем ко всем числам на отрезке) | ||
+ | t[v].min += t[v].add; | ||
+ | |||
+ | // В детях это изменение еще не учтено, пропушим его в них | ||
+ | t[v * 2 + 1].add += t[v].add; | ||
+ | t[v * 2 + 2].add += t[v].add; | ||
+ | |||
+ | // После применения отложенной операции, занулим t[v].add, чтобы позже не прибавить еще раз | ||
+ | t[v].add = 0; | ||
+ | } | ||
+ | |||
+ | // Прибавить x на отрезке | ||
+ | // v - вершина | ||
+ | // [tl, tr) - отрезок вершины ДО (правая граница не включается) | ||
+ | // [l, r) - отрезок запроса (правая граница не включается) | ||
+ | // x - то, что хотим прибавить на отрезке | ||
+ | void update(int v, int tl, int tr, int l, int r, int x) { | ||
+ | // вершина дерева вообще не попадает в отрезок запроса, ничего не делаем | ||
+ | if (r <= tl || tr <= l) return; | ||
+ | |||
+ | // вершина дерева полностью попадает в отрезок запроса | ||
+ | if (l <= tl && tr <= r) { | ||
+ | // скажем, что когда-нибудь потом в этой вершине нужно будет прибавить x | ||
+ | t[v].add += x; | ||
+ | return; | ||
+ | } | ||
+ | |||
+ | // если мы попали сюда, значит вершина дерева пересекается с отрезком запроса, и нужно спускаться в детей. | ||
+ | // но возможно, в текущей вершине есть отложенная операция, которую нужно применить к детям, поэтому вызовем push | ||
+ | push(v); | ||
+ | |||
+ | // спускаемся в детей | ||
+ | int tm = tl + (tr - tl) / 2; | ||
+ | update(v * 2 + 1, tl, tm, l, r, x); | ||
+ | update(v * 2 + 2, tm, tr, l, r, x); | ||
+ | |||
+ | // в нашей вершине точно нет отложенной операции, потому что выше вызвали push, поэтому можно просто | ||
+ | // пересчитать min из детей. Так как в детях могут быть отложенные операции, то получим значения в них, используя get | ||
+ | t[v].min = min(get(v * 2 + 1), get(v * 2 + 2)); | ||
+ | } | ||
+ | |||
+ | // Получить минимум на отрезке | ||
+ | // v - вершина | ||
+ | // [tl, tr) - отрезок вершины ДО (правая граница не включается) | ||
+ | // [l, r) - отрезок запроса (правая граница не включается) | ||
+ | ll get(int v, int tl, int tr, int l, int r) { | ||
+ | // вершина дерева вообще не попадает в отрезок запроса, ничего не делаем | ||
+ | if (r <= tl || tr <= l) { | ||
+ | return INF; | ||
+ | } | ||
+ | |||
+ | // вершина дерева полностью попадает в отрезок запроса | ||
+ | if (l <= tl && tr <= r) { | ||
+ | // вернем минимум с учетом отложенной операции | ||
+ | return get(v); | ||
+ | } | ||
+ | |||
+ | // если мы попали сюда, значит вершина дерева пересекается с отрезком запроса, и нужно спускаться в детей. | ||
+ | // но возможно, в текущей вершине есть отложенная операция, которую нужно применить к детям, поэтому вызовем push | ||
+ | push(v); | ||
+ | |||
+ | // получаем ответы из детей и берем минимум из них | ||
+ | int tm = tl + (tr - tl) / 2; | ||
+ | ll a = get(v * 2 + 1, tl, tm, l, r); | ||
+ | ll b = get(v * 2 + 2, tm, tr, l, r); | ||
+ | return min(a, b); | ||
+ | } | ||
</syntaxhighlight> | </syntaxhighlight> |
Версия 11:20, 10 января 2021
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 }