Дерево отрезков
Определение
Дерево отрезков - структура данных, позволяющая выполнять многие операции с отрезками массива за \(O(\log N)\). Дерево отрезков - универсальная структура данных, для которой можно реализовать неограниченный набор операций (иногда за большую сложность: \(O(\log^2 N)\)). Самая простая версия дерева отрезков позволяет находить сумму или минимум на отрезке, и изменять отдельные элементы.
Построение дерева отрезков
Дерево отрезков - полное бинарное дерево, в котором каждая вершина отвечает за некоторый отрезок в массиве. Корень дерева отвечает за весь массив, его две дочерних вершины - за две половины, и так далее. У каждой вершины, отвечающей за отрезок длиной больше \(1\), есть две дочерних вершины, отвечающих за левую и правую половины этого отрезка. Листья дерева отрезков отвечают за отдельные элементы (отрезки длиной \(1\)).
Графически это выглядит следующим образом (для массива из 8 элементов):
Каждый прямоугольник - вершина дерева отрезков. Если некоторая вершина отвечает за отрезок нечётной длины, то одна из её дочерних вершин будет отвечать за отрезок длиной \(\lceil {n \over 2} \rceil\), а другая - за отрезок длиной \(\lfloor {n \over 2} \rfloor\). Например, так выглядит дерево отрезков для массива из 13 элементов:
Для массива из \(n\) элементов дерево отрезков имеет около \(2n\) вершин (\(n + {n \over 2} + {n \over 4} + \ldots\)), а его высота равна порядка \(\log n\).
Главное свойство дерева отрезков, на котором и строятся все алгоритмы работы с ним: любой непрерывный отрезок в массиве из \(n\) элементов можно представить с помощью около \(2 \log n\) вершин в дереве отрезков.
Например, отрезок \([1; 11]\) в массиве длиной \(13\) можно представить с помощью следующих вершин:
Дерево отрезков для поиска суммы
Одна из простейших функций, которую можно считать за \(O(\log N)\) с помощью дерева отрезков - сумма.
При построении дерева в каждой его вершине сохраним сумму на соответствующем отрезке (построение будет вестись рекурсивно, поэтому достаточно просто сложить суммы на двух дочерних отрезках). Затем каждый запрос суммы на отрезке будем разбивать на \(2 \log N\) отрезков, и находить сумму на каждом из них за \(O(1)\), используя предпросчитанные значения. Таким образом сложность запроса суммы равна \(O(\log N)\).
Кроме запросов суммы к дереву отрезков также могут поступать запросы на изменение отдельных элементов (модификацию). Заметим, что от изменения одного элемента значение суммы изменится в одной вершине на каждом уровне дерева отрезков (в которую входит этот элемент). Пересчитаем значения суммы (опять же, рекурсивно) только в этих вершинах. Таким образом сложность запроса модификации равна высоте дерева, или \(O(\log N)\).
Для реализации запроса суммы и запроса модификации обход дерева реализуется с помощью одного и того же алгоритма, основанного на DFS. Пусть границы нашего запроса \([L; R]\) (в случае запроса модификации \(L = R\)), а границы отрезка, соответствующего текущей вершине \([TL; TR]\). В зависимости от взаимного положения этих границ, существуют три варианта действий алгоритма:
-
Текущий отрезок полностью входит в запрос (\(L \le TL; TR \le R\)).
Если это запрос суммы, вернём предпросчитанную сумму на отрезке. Если это запрос модификации, изменим элемент и пересчитаем сумму. В дочерние вершины спускаться нет надобности.
-
Текущий отрезок полностью не входит в запрос (\(TR < L\) или \(R < TL\)).
Никаких действий выполнять не нужно, просто выйдем из функции. Если это запрос суммы, просто вернём \(0\).
-
Текущий отрезок частично входит в запрос.
Вызовем функцию рекурсивно для двух дочерних отрезков. Если это запрос суммы, вернём сумму двух полученных значений. Если это запрос модификации, пересчитаем значение суммы для текущего отрезка (так как оно могло измениться).
Обозначим эти варианты соответственно зелёным, красным и жёлтым цветом. Тогда запрос суммы на отрезке \([1; 11]\) массива длиной \(13\) будет обработан следующим образом:
А запрос модификации \(4\)-го элемента:
Реализация дерева отрезков для поиска суммы
Полное бинарное дерево представляем, как и, например, кучу, с помощью массива и формул перехода \(l = 2v\) и \(r = 2v + 1\). Для предотвращения всех возможных переполнений размер дерева отрезков для массива из \(n\) элементов принимают равным \(4n\).
Реализация на C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100000]; //массив
int tree[400004]; //дерево отрезков. в вершинах хранятся суммы
//Построение дерева по изначальному массиву.
//v - номер текущей вершины; tl, tr - границы соответствующего отрезка
void build_tree(int v, int tl, int tr) {
if (tl == tr) {
tree[v] = a[tl]; //сумма отрезка из одного элемента равна этому элементу
} else {
//tm - средний элемент отрезка.
//отрезок разбивается на два отрезка [tl; tm], [tm + 1; tr]
int tm = (tl + tr) / 2;
build_tree(v * 2, tl, tm);
build_tree(v * 2 + 1, tm + 1, tr);
tree[v] = tree[v * 2] + tree[v * 2 + 1];
}
}
//Запрос суммы
//l, r - границы запроса;
//v - номер текущей вершины; tl, tr - границы соответствующего отрезка
int get_sum(int l, int r, int v, int tl, int tr) {
//вариант 1
if (l <= tl && tr <= r) {
return tree[v];
}
//вариант 2
if (tr < l || r < tl) {
return 0;
}
//вариант 3
int tm = (tl + tr) / 2;
return get_sum(l, r, v * 2, tl, tm)
+ get_sum(l, r, v * 2 + 1, tm + 1, tr);
}
//Запрос модификации
//idx - индекс элемента, val - новое значение
//v - номер текущей вершины; tl, tr - границы соответствующего отрезка
void update(int idx, int val, int v, int tl, int tr) {
//вариант 1
if (idx <= tl && tr <= idx) { //То же, что и idx == tl == tr
a[idx] = val;
tree[v] = val;
return;
}
//вариант 2
if (tr < idx || idx < tl) {
return;
}
//вариант 3
int tm = (tl + tr) / 2;
update(idx, val, v * 2, tl, tm);
update(idx, val, v * 2 + 1, tm + 1, tr);
tree[v] = tree[v * 2] + tree[v * 2 + 1];
}
int main() {
//Ввод массива...
build_tree(1, 0, n - 1); //параметры корня дерева.
//все запросы должны вызываться для этих параметров.
//Можно делать запросы вида get_sum(l, r, 1, 0, n - 1) и update(idx, val, 1, 0, n - 1);
}
Реализация дерева отрезков для поиска минимума
Для поиска минимума нужно изменить в предыдущей реализации всего лишь несколько строк:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100000]; //массив
int tree[400004]; //дерево отрезков. в вершинах хранятся минимумы
void build_tree(int v, int tl, int tr) {
if (tl == tr) {
tree[v] = a[tl];
} else {
int tm = (tl + tr) / 2;
build_tree(v * 2, tl, tm);
build_tree(v * 2 + 1, tm + 1, tr);
tree[v] = min(tree[v * 2], tree[v * 2 + 1]); //сохраняем минимум вместо суммы
}
}
//Запрос минимума
int get_min(int l, int r, int v, int tl, int tr) {
//вариант 1
if (l <= tl && tr <= r) {
return tree[v];
}
//вариант 2
if (tr < l || r < tl) {
return INT_MAX; //Значение, которое не повлияет на общий минимум
}
//вариант 3
int tm = (tl + tr) / 2;
return min(get_min(l, r, v * 2, tl, tm), //минимум вместо суммы.
get_min(l, r, v * 2 + 1, tm + 1, tr));
}
void update(int idx, int val, int v, int tl, int tr) {
//вариант 1
if (idx <= tl && tr <= idx) { //То же, что и idx == tl == tr
a[idx] = val;
tree[v] = val;
return;
}
//вариант 2
if (tr < idx || idx < tl) {
return;
}
//вариант 3
int tm = (tl + tr) / 2;
update(idx, val, v * 2, tl, tm);
update(idx, val, v * 2 + 1, tm + 1, tr);
tree[v] = min(tree[v * 2], tree[v * 2 + 1]); //минимум вместо суммы.
}
int main() {
//Ввод массива...
build_tree(1, 0, n - 1); //параметры корня дерева.
//все запросы должны вызываться для этих параметров.
//Можно делать запросы вида get_min(l, r, 1, 0, n - 1) и update(idx, val, 1, 0, n - 1);
}
Деревья отрезков, сохраняющие все элементы
Для решения некоторых задач вершина, отвечающая за отрезок, должна хранить все элементы этого отрезка в порядке сортировки. Может показаться, что это займёт слишком много памяти, но это не так. Каждый элемент массива хранится единожды на каждом уровне дерева, которых \(\log n\). Значит, вся структура данных занимает \(O(N \log N)\) памяти.
Классической задачей на дерево отрезков такого вида является следующая:
Дан массив из \(N\) чисел, к которому поступает \(M\) запросов. Запросы имеют вид \((l, r, x)\). На каждый запрос нужно ответить, сколько элементов, больше либо равных \(x\), содержится на отрезке \([l; r]\).
Для решения этой задачи будем в каждой вершине дерева отрезков хранить отсортированный
std::vector, содержащий все элементы соответствующего отрезка. Для
ответа на запрос будем использовать функцию std::lower_bound. Она
позволяет отвечать на запрос для одной вершины за \(O(\log N)\), поэтому общая
сложность ответа на запрос будет равна \(O(\log^2 N)\).
Реализация на C++:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100000]; //массив
vector<int> tree[400004]; //дерево отрезков. в вершинах хранятся все элементы
void build_tree(int v, int tl, int tr) {
if (tl == tr) {
tree[v].push_back(a[tl]);
} else {
int tm = (tl + tr) / 2;
build_tree(v * 2, tl, tm);
build_tree(v * 2 + 1, tm + 1, tr);
//Для слияния используется библиотечная функция std::merge,
//но его можно реализовать и вручную.
tree[v].resize(tr - tl + 1);
merge(tree[v * 2].begin(), tree[v * 2].end(),
tree[v * 2 + 1].begin(), tree[v * 2 + 1].end(),
tree[v].begin());
}
}
//Запрос (l; r; x)
//Возвращает количество искомых элементов.
int query(int l, int r, int x, int v, int tl, int tr) {
//вариант 1
if (l <= tl && tr <= r) {
return tree[v].end() - lower_bound(tree[v].begin(), tree[v].end(), x);
}
//вариант 2
if (tr < l || r < tl) {
return 0;
}
//вариант 3
int tm = (tl + tr) / 2;
return query(l, r, x, v * 2, tl, tm)
+ query(l, r, x, v * 2 + 1, tm + 1, tr);
}
int main() {
//Ввод массива...
build_tree(1, 0, n - 1); //параметры корня дерева.
//все запросы должны вызываться для этих параметров.
//Можно делать запросы вида query(l, r, x, 1, 0, n - 1)
}
Если в подобных задачах допускается модификация элементов, то вместо
std::vector нужно хранить std::multiset, который
позволяет быстро удалять и добавлять элементы. Но в таком случае мы уже
не сможем отвечать на запросы количества элементов, так как итераторы
std::multiset нельзя отнимать друг от друга.
Дерево отрезков с массовым обновлением. Несогласованные поддеревья
Благодаря определённой модификации, дерево отрезков может выполнять обновление элементов (увеличение или присваивание) на отрезках произвольной длины за \(O(\log N)\). Эта модификация достаточно общая, и позволяет решать с помощью дерева отрезков целый класс новых задач.
Идея заключается в следующем. Пусть в процессе выполнения запроса присваивания на отрезке мы спустились в вершину, полностью принадлежащую этому отрезку. По логике нам нужно изменить значение в этой вершине, и во всех вершинах её поддерева. Но сложность такой операции неприемлемо высока: \(O(N \log N)\).
Вместо этого мы поступаем следующем образом: изменяем значение только в самой вершине, не обновляя её поддерево (таким образом, в поддереве теперь хранятся устаревшие некорректные значения), и запоминаем, что у этой вершины есть несогласованная модификация. На этом выполнение запроса для вершины и её поддерева завершено.
Если последующие запросы не будут обращаться к поддереву с несогласованной модификацией, то они будут выполняться корректно. Но рано или поздно может поступить запрос, который требуется обработать индивидуально для дочерних вершин с несогласованной модификацией. В этом случае мы поступаем просто: передадим модификацию дочерним вершинам (только дочерним вершинам, а не всему поддереву). Теперь данная вершина согласована, а несогласованность перешла к её дочерним. Такая операция называется проталкиванием модификации.
Возможно, для обработки запроса требовались только дочерние вершины, и одного проталкивания хватит. Если же запрос будет спускаться ниже по поддереву, по мере его спуска будем проталкивать модификацию всё ниже и ниже. Проталкивание выполняется за \(O(1)\) одновременно с разделением запроса, поэтому на асимптотику это никак не повлияет.
Для примера, пусть мы работаем с деревом отрезков для поиска суммы с массовым присваиванием. Мы присвоили отрезку \([0; 6]\) значение \(x\). Изменим значение суммы в вершине, отвечающей за этот отрезок (установим его равным \(7x\)), и установим для этой вершины параметр несогласованной модификации равным \(x\).
Синий квадрат обозначает наличие у вершины несогласованной модификации.
Теперь обработаем запрос нахождения суммы на отрезке \([6; 7]\):
Как видите, несогласованность перешла к отрезкам \([0; 3]\) и \([4; 5]\). Она перешла бы и к отрезку \([6; 6]\), но у него нет дочерних вершин, поэтому несогласованность устраняется.
Реализация дерева отрезков для поиска суммы с массовым присваиванием
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;
int n;
int a[100000]; //массив
int tree[400004]; //дерево отрезков. в вершинах хранятся суммы
int mod[400004]; //массив для хранения модификаций. 0 обозначает отсутствие
//модификаций, любое другое число - присвоенное значение.
void build_tree(int v, int tl, int tr) {
if (tl == tr) {
tree[v] = a[tl];
} else {
int tm = (tl + tr) / 2;
build_tree(v * 2, tl, tm);
build_tree(v * 2 + 1, tm + 1, tr);
tree[v] = tree[v * 2] + tree[v * 2 + 1];
}
}
//Проталкиваем модификации вершины v её дочерним вершинам.
void push(int v, int tl, int tr) {
if (mod[v] != 0 && v * 2 + 1 < 400004) { //если есть что и куда проталкивать
//проталкиваем несогласованность
mod[v * 2] = mod[v * 2 + 1] = mod[v];
mod[v] = 0;
//и пересчитываем значения
int tm = (tl + tr) / 2;
tree[v * 2] = (tm - tl + 1) * mod[v * 2];
tree[v * 2 + 1] = (tr - tm) * mod[v * 2 + 1];
}
}
//Запрос суммы
int get_sum(int l, int r, int v, int tl, int tr) {
//вариант 1
if (l <= tl && tr <= r) {
return tree[v];
}
//вариант 2
if (tr < l || r < tl) {
return 0;
}
//вариант 3
push(v, tl, tr); //Проталкиваем модификации перед каждым разделением запроса!
int tm = (tl + tr) / 2;
return get_sum(l, r, v * 2, tl, tm)
+ get_sum(l, r, v * 2 + 1, tm + 1, tr);
}
//Запрос присваивания значения val отрезку [l;r]
void assign(int l, int r, int val, int v, int tl, int tr) {
//вариант 1
if (l <= tl && tr <= r) {
tree[v] = val * (tr - tl + 1);
mod[v] = val; //сохраняем несогласованность
return;
}
//вариант 2
if (tr < l || r < tl) {
return;
}
//вариант 3
push(v, tl, tr); //Проталкиваем модификации перед каждым разделением запроса!
int tm = (tl + tr) / 2;
assign(l, r, val, v * 2, tl, tm);
assign(l, r, val, v * 2 + 1, tm + 1, tr);
tree[v] = tree[v * 2] + tree[v * 2 + 1];
}
int main() {
//Ввод массива...
build_tree(1, 0, n - 1); //параметры корня дерева.
//все запросы должны вызываться для этих параметров.
//Можно делать запросы вида get_sum(l, r, 1, 0, n - 1) и assign(l, r, val, 1, 0, n - 1);
}