Динамическое(Неявное) Дерево Отрезков
Содержание
Задача
Дана прямая длинной $n$ ($1 \le n \le 10^9$), есть запросы двух видов :
Отметить на прямой все точки с координатами с $l$ по $r$, если точка уже отмечена отмечать второй раз не нужно.
Вывести количество отмеченных точек на отрезке с $l$ по $r$.
Идея
Все ранее рассмотренные задачи на Дерево отрезков мы разбирали на массиве, когда все координаты были достаточно маленькие, что же делать в случаях, когда координаты порядка 1e9.
Асимптотика
Первым делом а давайте поймем сколько вообще отрезков мы создадим. На каждый запрос мы создадим $O(\log(n))$ отрезков, то есть суммарно появится не более $O(q\log(n))$ отрезков
Наивная, но иногда хорошая работающая идея
Давайте хранить все состояние в unordered_map и создавать их только тогда, когда они понадобятся
Альтернативный способ
Давайте создадим структуру, в которой будет хранится ответ на отрезке и указатель на правого и левого сына или нулевой указатель, если их нет, тогда вершина будет создаваться только тогда когда к ней есть запрос
Оптимизация
У указателя есть некоторые проблемы, например на некоторых системах он всегда занимает 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