Дерево отрезков
Запрос на отрезке и модификация отдельных элементов
- Если отрезок текущей вершины не пересекается с отрезком запроса, то возвращается нейтральное значение.
- Если отрезок текущей вершины целиком включён в отрезок запроса, то возвращается значение, хранящееся в текущей вершине.
- Во всех остальных случаях запрос перенаправляется потомкам текущей вершины.
Можно выделить два распространённых способа реализации данной логики:
if (l > r) //отрезки не пересекаются if (l == vl && vr == r) //отрезок текущей вершины принадлежит отрезку запроса query(2 * v + 1, vl, vm, l, min(r, vm)); query(2 * v + 2, vm + 1, vr, max(l, vm + 1), r);
struct SegmentTree < int size; vectort; void build(int v, int vl, int vr, vector &a) < if (vl == vr) < t[v] = a[vl]; return; >int vm = vl + (vr - vl) / 2; build(2 * v + 1, vl, vm, a); build(2 * v + 2, vm + 1, vr, a); t[v] = t[2 * v + 1] + t[2 * v + 2]; > long long query(int v, int vl, int vr, int l, int r) < if (vr < l || r < vl) return 0; if (l void modify(int v, int vl, int vr, int index, int value) < if (vr < index || index < vl) return; if (vl == vr) < t[v] += value; return; >int vm = vl + (vr - vl) / 2; modify(2 * v + 1, vl, vm, index, value); modify(2 * v + 2, vm + 1, vr, index, value); t[v] = t[2 * v + 1] + t[2 * v + 2]; > SegmentTree(vector &a) : size(a.size()), t(4 * a.size()) < build(0, 0, size - 1, a); >long long getSum(int l, int r) < return query(0, 0, size - 1, l, r); >void addValue(int index, int value) < modify(0, 0, size - 1, index, value); >>;
Запрос на отрезке и модификация на отрезке
- Считаем, что актуальное значение в вершине v равно t[v] + add[v] * (vr - vl + 1).
- Перед выводом результата или передачей запроса будем спускать значение add[v] потомкам текущей вершины при помощи функции push().
struct SegmentTree < int size; vectort, tAdd; void build(int v, int vl, int vr, vector &a) < if (vl == vr) < t[v] = a[vl]; return; >int vm = vl + (vr - vl) / 2; build(2 * v + 1, vl, vm, a); build(2 * v + 2, vm + 1, vr, a); t[v] = t[2 * v + 1] + t[2 * v + 2]; > void push(int v, int vl, int vr) < if (tAdd[v]) < t[v] += (vr - vl + 1) * tAdd[v]; if (vl < vr) < tAdd[2 * v + 1] += tAdd[v]; tAdd[2 * v + 2] += tAdd[v]; >tAdd[v] = 0; > > long long query(int v, int vl, int vr, int l, int r) < push(v, vl, vr); if (vr < l || r < vl) return 0; if (l void modify(int v, int vl, int vr, int l, int r, int value) < push(v, vl, vr); if (vr < l || r < vl) return; if (l int vm = vl + (vr - vl) / 2; modify(2 * v + 1, vl, vm, l, r, value); modify(2 * v + 2, vm + 1, vr, l, r, value); t[v] = t[2 * v + 1] + t[2 * v + 2]; > SegmentTree(vector &a) : size(a.size()), t(4 * a.size()), tAdd(4 * a.size()) < build(0, 0, size - 1, a); >long long getSum(int l, int r) < return query(0, 0, size - 1, l, r); >void addValue(int l, int r, int value) < modify(0, 0, size - 1, l, r, value); >>;
Почему для хранения дерева отрезков требуется массив размера 4n?
Пусть для массива a[] из n элементов создаётся дерево отрезков, хранящееся в массиве t[]. Правило требует, чтобы размер массива t[] был не менее 4n.
Однако можно рассуждать следующим образом: двоичным деревом с наибольшим количеством элементов является полное двоичное дерево. Если количество листьев в полном двоичном дереве равно n, то общее количество вершин в нём равно 2n — 1. Возможно ли, что для хранения дерева отрезков всегда будет достаточно массива размера 2n?
К сожалению, это не так. Процедура build не обязательно формирует полное двоичное дерево; некоторые элементы массива t[] могут не использоваться. Например, если n = 5, то дерево отрезков имеет высоту 4 и содержит 9 элементов. Если N = 10, объединяются два таких дерева высоты 4, и на нижнем уровне появляются 6 неиспользуемых элементов (t[17]..t[22]).
Оценим более точно требуемый размер массива t[].
Прежде всего определим вспомогательные функции leftHalf(n) и rightHalf(n), возвращающие размер левого и правого поддеревьев дерева отрезков для массива a[] из n элементов (n > 1). Если n чётно, то обе функции возвращают n / 2. Если n нечётно, то средний элемент относится к левой части.
int leftHalf(int n) < return n / 2 + n % 2; >int rightHalf(int n) < return n / 2; >
Далее определим функцию height(n), возвращающую высоту дерева отрезков для массива a[] из n элементов. Если n = 1, то height(n) = 1. В других случаях height(n) = 1 + max(height(leftHalf(n)), height(rightHalf(n))); так как левое поддерево всегда не меньше правого, эту запись можно упростить: height(n) = 1 + height(leftHalf(n)).
Кроме того, определим функцию fullSize(h), возвращающую размер полного двоичного дерева высоты h.
int height(int n) < if (n == 1) return 1; else return 1 + height(leftHalf(n)); >int fullSize(int h)
Наконец, определим функцию tSize(n), возвращающую размер t[] для массива a[] из n элементов. Если n = 1, то tSize(n) = 1. Далее, если левое и правое поддерево имеют одинаковую высоту, то необходимый размер t[] определяется последним (нижним) элементом правого поддерева, а левое поддерево становится полным: tSize(n) = 1 + fullSize(height(leftHalf(n))) + tSize(rightHalf(n)). Если же левое поддерево выше правого, то необходимый размер t[] определяется последним (нижним) элементом левого поддерева, а правое поддерево становится полным: tSize(n) = 1 + tSize(leftHalf(n)) + fullSize(height(rightHalf(n))).
Можно видеть, что график функции tSize практически всегда находится выше графика функции 2x и всегда ниже графика функции 4x. Например, tSize(8448) = 32705, что значительно превышает не только удвоенный, но и утроенный размер исходного массива.
Ссылки
- Codeforces EDU — Дерево отрезков: часть 1, часть 2
- e-maxx.ru — Дерево отрезков
- neerc.ifmo.ru/wiki — Дерево отрезков
- brestprog — Дерево отрезков
- Копелиович С. Лекция про структуры данных Зимней школы МФТИ
- i.cs.hku.hk — Segment Trees: Applications
- sharmaeklavya2.github.io — Generalizing Segment Trees
- Ibtehaz N. Multidimensional segment trees can do range queries and updates in logarithmic time
Источник
Дерево отрезков: просто и быстро
Накануне очередного запуска курса «Алгоритмы для разработчиков» мы провели открытый урок. На нём поговорили об известной идее дерева отрезков, обсудили, как его строить, обновлять и быстро O(log n) вычислять сумму чисел любого отрезка данного массива. Алгоритм очень простой и экономный: нужно O(n) памяти. Для закрепления материала решили олимпиадную задачу.
Вебинар провёл опытный программист и преподаватель, а также руководитель курса «Алгоритмы для разработчиков» Евгений Волосатов.
Присказка
Дерево отрезков — это структура данных, которая позволяет алгоритмически просто и логарифмически быстро находить сумму элементов массива на заданном отрезке.
К примеру, представьте, что надо найти сумму следующих чисел:
При этом нам нужно не просто вычислить сумму чисел указанной последовательности (сумму элементов определённого массива), а максимально быстро найти сумму любой последовательности из этих чисел. То есть мы можем задать какой-нибудь интервал (отрезок) и максимально быстро дать ответ, чему равна сумма чисел из этого интервала:
Что значит быстро? Это значит быстрее, чем, если бы мы просто суммировали числа. Ведь чисел может быть и миллионы, и миллиарды…
Именно желание быстро находить сумму последовательных элементов и стало мотивацией нашего вебинара. Причём, речь идёт не только о сумме, но и о других задачах, например, вычислении любой ассоциативной функции. Таким образом, мы говорим об операциях, выполнение которых не зависит от порядка вычисления.
Возвратимся к нашему ряду:
Очевидно, что если мы хотим находить результат быстро, нужно посчитать некоторые суммы заранее. Первое, что приходит на ум, складывать попарно:
Теперь, если нужно найти сумму чисел, мы можем сделать это практически моментально. Например, чтобы найти сумму упомянутого выше отрезка, достаточно будет 13 прибавить к 9. Всё элементарно: для нахождения суммы четырёх чисел мы сложили только два.
Чтобы найти сумму этого отрезка, нам нужно сложить элементы, которые, так или иначе, покрывают наш отрезок:
Разумеется, 3 + 13 + 19 = 35. Обратите внимание, чтобы найти сумму семи чисел, мы сложили только три. Если бы отрезок состоял из тысячи элементов, достаточно было бы сложить в среднем 10 элементов, так как мы имеем логарифмическую сложность с логарифмом по основанию 2. И это быстро!
Полное двоичное дерево
Полное двоичное дерево — это дерево, у каждого элемента которого есть ровно два дочерних элемента.
Для работы с полным двоичным деревом можно и нужно использовать такую структуру данных, как массив. Нумеровать этот массив удобно с единицы. Пронумеруем каждый элемент двоичного дерева натуральными числами от 1 до 2 n -1:
Вся красота подхода в том, что очень легко вычислять номер детей и родителей.
Формула вычисления «левого ребёнка»: i*2, «правого»: i*2+1.
Например, вычислим номера детей у пятого элемента:
А как от «ребёнка» подняться к «родителю»? Используем целочисленное деление i / 2
Ок, а как определить, левый ребёнок или правый? Ответ следующий: у левых детей чётные номера, у правых — нечётные.
Возвратившись к нашему примеру бинарного дерева, зададимся вопросом, как нам его построить? Смотрите, у нас вначале есть массив чисел:
Для него нужно построить двоичное дерево. Сколько потребуется памяти для хранения двоичного дерева, внизу которого находятся эти элементы?
Ответ на этот вопрос — 2n, если n является степенью двойки.
Идём дальше, ведь перед нами возникают ещё два вопроса:
- с какого элемента необходимо разместить исходные числа в массиве полного двоичного дерева?
- с какого элемента и в какую сторону мы начнём заполнять наше дерево предварительно рассчитанными суммами?
Ответить на первый вопрос достаточно просто: у нас 8 элементов, всего в массиве будет 16 элементов, значит, первый элемент будет под номером 16 — 8 = 8. И начинать строить мы будем слева-направо и снизу-вверх, начиная с 7 элемента, складывая значения у детей, вот так:
Далее необходимо определить, как именно находить сумму нужного отрезка. Вернёмся к нашему первому примеру, пронумеруем элементы и зададим отрезок, причём обозначим первый элемент в отрезке, который нужно сложить, буквой L, а последний — R:
Теперь необходимо ввести ещё одно понятие, чтобы был ясен алгоритм действий. Речь идёт о понятии фундаментальных элементов и соответствующих им фундаментальных отрезков. Фундаментальный элемент — это какой угодно элемент из всего массива, и ему соответствует фундаментальный отрезок, то есть те элементы из начального массива, которые являются его непосредственными детьми/внуками. Для фундаментального элемента с номером 4 “5” фундаментальный отрезок будет с 8 по 9 элемент: [“2”; “3”]:
Что касается фундаментального элемента с номером 10 — “7” (мы обозначили его L), он совпадает со своим фундаментальным отрезком. Можно ли расширить этот фундаментальный отрезок, не выходя за пределы L-R? В нашем случае можно. Правило для левой границы такое: если это левый ребёнок, то фундаментальный отрезок можно расширить, новый фундаментальный элемент будет являться родителем текущего. То есть мы можем в программе писать следующее:
Теперь перейдём к правому элементу R. Он является фундаментальным элементом и левым ребёнком, поэтому расширить область мы уже не можем (выйдем за пределы отрезка). Значит, можем добавить этот элемент к ответу:
Далее нужно, чтобы левый элемент двигался к правому, а правый — к левому. Для левого элемента с индексом L = 10 следующий индекс равен 5, т. к. он пойдёт к родителю. Но пойдёт сначала вправо, а потом вверх:
Итак, значение L перешло на уровень выше и немного правее. Как же будет уменьшаться R? С помощью формулы (R – 1) / 2.
Вот такой алгоритм. Что касается следующих значений переменных L и R, то далее они будут перемещаться следующим образом:
Если же в дереве будет не 8 элементов, а неудобное число, скажем 12, нам придётся дополнить дерево (двоичное дерево должно быть полным) до 16-ти.
Формула для вычисления количества элементов (берётся целая часть логарифма):
Теперь вычислим ассоциативную функцию нахождения минимума. Вот наше дерево и отрезок:
Как думаете, сколько раз в нашей функции будет задействован элемент № 5 — один или два? Разумеется, один, но каким образом это проверяется в алгоритме? На самом деле, этот элемент является либо левым, либо правым сыном, а значит, выполнится действие либо для L, либо для R.
+
Теперь рассмотрим операцию изменения. Допустим, изменился какой-нибудь элемент, например, вместо 7 пришёл 0. Чтобы наше дерево отрезков осталось в рабочем состоянии, необходимо обновить всех родителей, причём нужно идти до самого верха.
Решение олимпиадной задачи
Одно из требований к таким задачам — всё должно работать быстро. Итак, имеем следующее условие:
Будем решать её, используя знания о дереве отрезков. В результате получим следующий код на C#:
Отправляем на проверку, видим, что решение принято и является полным, а значит, наш алгоритм работает.
На этом всё, если хотите подробностей, смотрите видео целиком. Также можете на досуге почитать следующие авторские статьи нашего преподавателя Евгения Волосатова на Хабре:
Источник