Альтернативная реализация Дерева Отрезков с отложенными операциями
Материал из Algocode wiki
Версия от 11:24, 10 января 2021; Forestryks (обсуждение | вклад)
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