Динамическое(Неявное) Дерево Отрезков

Материал из Algocode wiki
Версия от 22:48, 31 января 2020; Глеб (обсуждение | вклад)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Задача

Дана прямая длинной $n$ ($1 \le n \le 10^9$), есть запросы двух видов :

Отметить на прямой все точки с координатами с $l$ по $r$, если точка уже отмечена отмечать второй раз не нужно.

Вывести количество отмеченных точек на отрезке с $l$ по $r$.

Идея

Все ранее рассмотренные задачи на Дерево отрезков мы разбирали на массиве, когда все координаты были достаточно маленькие, что же делать в случаях, когда координаты порядка 1e9.

Асимптотика

Первым делом а давайте поймем сколько вообще отрезков мы создадим. На каждый запрос мы создадим $O(\log(n))$ отрезков, то есть суммарно появится не более $O(q\log(n))$ отрезков

Наивная, но иногда хорошая работающая идея

Давайте хранить все состояния в unordered_map и создавать их только тогда, когда они понадобятся

Код

1 unordered_map<int, 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