Динамическое(Неявное) Дерево Отрезков
Дана прямая длинной $n$ ($1 \le n \le 10^9$), есть запросы двух видов :
Отметить на прямой все точки с координатами с $l$ по $r$, если точка уже отмечена отмечать второй раз не нужно.
Вывести количество отмеченных точек на отрезке с $l$ по $r$.
Все ранее рассмотренные задачи на Дерево отрезков мы разбирали на массиве, когда все координаты были достаточно маленькие, что же делать в случаях, когда координаты порядка 1e9.
Первым делом а давайте поймем сколько вообще отрезков мы создадим. На каждый запрос мы создадим $O(\log(n))$ отрезков, то есть суммарно появится не более $O(q\log(n))$ отрезков
Давайте хранить все состояния в unordered_map и создавать их только тогда, когда они понадобятся
1 unordered_mapint, int> seg_tree; 2 //если вы обратитесь к элементу, которого нет в unordered_map, то он будет равен 0, то для данной задачи нам можно обращаться, как и в обычном ДО
Давайте создадим структуру, в которой будет хранится ответ на отрезке и указатель на правого и левого сына или нулевой указатель, если их нет, тогда вершина будет создаваться только тогда когда к ней есть запрос
У указателя есть некоторые проблемы, например на некоторых системах он всегда занимает 8 байт и это может вызвать мл, поэтому можно хранить вместо указателей массив структур и теперь указатель на левого и правого сына это просто их индекс в массиве или -1, если они пока не созданы
1 struct seg 2 int ans, l, r; 3 seg() 4 ans = 0; 5 l = -1; 6 r = -1; 7 > 8 >; 9 10 seg seg_tree[SZ]; 11 int sz = 0; 12 13 int get(..) 14 .. 15 if (seg_tree[now].l == -1) 16 seg_tree[now].l = sz++; 17 > 18 if (seg_tree[now].r == -1) 19 seg_tree[now].r = sz++; 20 > 21 .. 22 >
Автор конспекта: Глеб Лобанов
По всем вопросам пишите в telegram @glebodin
Источник
Дерево отрезков на указателях
В этой статье мы реализуем дерево отрезков для точечных изменений и суммы на отрезке. Наша первая реализация будет на указателях. Она не самая быстрая и компактная, но зато самая общая и понятная.
Замечание. Почти везде мы будем использовать полуинтервалы — обозначаемые как $[l, r)$ — вместо отрезков. Несмотря на контринтуитивность, это немного упростит код и вообще является хорошей практикой в программировании, подобно нумерации с нуля.
#Хранение в памяти
Каждая вершина дерева отрезков будет структурой, которая содержит ссылки на детей, свои границы $[l, r)$ и дополнительную нужную для задачи информацию — в нашем случае, сумму на отрезке.
Вершины будем создавать во время построения без какого-либо заданного порядка, поэтому ссылки на детей будут просто указателями на другую такую же структуру вершины-ребенка.
В олимпиадных задачах запросы часто подаются в формате «строка 0 k x для прибавления и 1 l r для суммы». Их можно парсить так:
Осталось собственно реализовать построение и запросы.
#Построение
Строить дерево отрезков можно рекурсивным конструктором, который создает детей, пока не доходит до листьев:
Если изначально массив не нулевой, то можно параллельно с проведением ссылок насчитывать суммы:
Альтернативно, можно либо потом отдельно пройтись по массиву и добавить каждое число по отдельности.
#Изменение
Для запроса прибавления будем рекурсивно спускаться вниз, пока не дойдем до листа, соответствующего элементу $k$, и на всех промежуточных вершинах прибавим $x$:
#Сумма
Для суммы сложнее — нужно делать разбор случаев, как отрезок запроса пересекается с отрезком вершины:
#Оптимизации
Данная реализация простая и расширяемая, но весьма неэффективная по времени и памяти, хотя ей можно сдать примерно 90% задач на олимпиадах по программированию.
Из относительно легких оптимизаций:
- Можно не хранить границы отрезка lb и rb , а пересчитывать их во время спуска.
- На 64-битных системах выгоднее использовать не new и указатели, а выделять вершины на массиве / векторе и использовать индексы относительно него: они будут весить 4 байта, а не 8.
Однако основная причина, почему реализация на указателях такая медленная, в том, что нужно много раз ходить по ссылкам, чтобы получать данные нужных вершин. Оказывается, можно избавиться от ссылок вообще, если ввести однозначную нумерацию вершин и расположить их в таком порядке на массиве — подробнее об этом можно почитать у Емакса и на CodeForces.
Источник
Дерево отрезков
Дерево отрезков — очень мощная и гибкая структура данных, позволяющая быстро отвечать на самые разные запросы на отрезках.
Рассмотрим конкретную задачу: дан массив $a$ из $n$ целых чисел, и требуется отвечать на запросы двух типов:
- Изменить значение в ячейке (т. е. реагировать на присвоение a[k] = x ).
- Вывести сумму элементов $a_i$ на отрезке с $l$ по $r$.
Оба запроса нужно обрабатывать за время $O(\log n)$.
Структура дерева отрезков
Чтобы решить задачу, сделаем с исходным массивом следующие манипуляции.
Посчитаем сумму всего массива и где-нибудь запишем. Потом разделим его пополам, посчитаем сумму на половинах и тоже где-нибудь запишем. Каждую половину потом разделим пополам ещё раз, и так далее, пока не придём к отрезкам длины 1.
Эту последовательность разбиений можно представить в виде дерева.
Корень этого дерева соответствует отрезку $[0, n)$, а каждая вершина (не считая листьев) имеет ровно двух сыновей, которые тоже соответствуют каким-то отрезкам. Отсюда и название — «дерево отрезков».
Разные полезные свойства
Высота дерева отрезков равна $\Theta(\log n)$: на каждом новом уровне длина отрезка уменьшается вдвое. Этот факт будет ключевым для оценки асимптотики операций.
Любой полуинтервал разбивается на $O(\log n)$ неперекрывающихся полуинтервалов, соответствующих в вершинам дерева: с каждого уровня нам достаточно не более двух отрезков.
Дерево содержит менее $2n$ вершин: первый уровень дерева отрезков содержит одну вершину (корень), второй уровень — в худшем случае две вершины, на третьем уровне в худшем случае будет четыре вершины, и так далее, пока число вершин не достигнет $n$. Таким образом, число вершин в худшем случае оценивается суммой $n + \frac + \frac + \frac + \ldots + 1 < 2n$. Значит, оно линейное по памяти.
При $n$, отличных от степеней двойки, не все уровни дерева отрезков будут полностью заполнены. Например, при $n=3$ левый сын корня есть отрезок $[0, 2)$, имеющий двух потомков, в то время как правый сын корня — отрезок $[2, 3)$, являющийся листом.
Ок, как это нам поможет?
Опишем, как с помощью такой структуры решить исходную задачу.
Запрос обновления. Нам нужно обновить значения в вершинах таким образом, чтобы они соответствовали новому значению $a[k] = x$.
Изменим все вершины, в суммах которых участвует $k$-тый элемент. Их будет $\Theta(\log n)$ — по одной с каждого уровня.
Это можно реализовать как рекурсивную функцию: ей передаётся текущая вершина дерева отрезков, и функция выполняет рекурсивный вызов от одного из двух своих сыновей (от того, который содержит $k$-ый элемент в своём отрезке), а после этого — пересчитывает значение суммы в текущей вершине точно таким же образом, как мы это делали при построении дерева отрезков.
Запрос суммы. Мы знаем, что во всех вершинах лежат корректные значения, и нам с помощью них посчитать сумму на отрезке.
Сделаем тоже рекурсивную функцию, рассмотрев три случая:
- Если отрезок вершины лежит целиком в отрезке запроса, то вернуть записанную в ней сумму.
- Если отрезки вершины и запроса не пересекаются, то вернуть 0.
- Иначе разделиться рекурсивно на 2 половины и вернуть сумму этой функции от обоих детей.
Чтобы разобраться, почему это работает за $O(\log n)$, нужно оценить количество «интересных» отрезков — тех, которые порождают новые вызовы рекурсии. Это будут только те, которые содержат границу запросов — остальные сразу завершатся. Обе границы отрезка содержатся в $O(\log n)$ отрезках, а значит и итоговая асимптотика будет такая же.
Дерево отрезков можно использовать для гораздо большего, чем только для суммы.
Далее этой главе мы рассмотрим разные реализации и варианты этой структуры и их применения.
Источник