Динамические структуры данных

Иногда в задачах требуется построить структуру данных на массиве очень большого размера (таком, что он не помещается в память). При этом известно, что количество запросов к структуре невелико. Типичная задача: Дан массив размером $n\ (1 \le n \le 10^9)$, изначально заполненный нулями. Необходимо ответить на $q\ (1 \le q \le 10^5)$ запросов одного из двух типов:

Изменить значение элемента.
Посчитать сумму на отрезке.

Решение

ЗамечаниеМы умеем решать эту задачу с помощью дерева отрезков, но сталкиваемся с недостатком памяти. Иногда это можно побороть, если воспользоваться техникой сжатия координат. Писать неявное ДО в такой ситуации — стрелять из пушки по воробьям.

Сделаем в дереве отрезков ряд изменений. Во-первых, напишем его на структурах и указателях. Каждая вершина дерева отрезков — это объект, который хранит указатели на своего левого и правого сына. Давайте решать эту задачу так, как мы решали бы ее обычным деревом отрезков, но не вызовем операцию построения. То есть изначально наше дерево отрезков — это корень. Создавать вершины мы будем в операциях обновления, если вершина еще не была создана (похожим на [отложенные операции] образом). При get-запросе считаем, что если вершина не создана, то сумма в ней 0 (логично ведь). Тогда за один запрос мы создадим $O(\log n)$ вершин, суммарно все будет работать за $O(q \log n)$ времени и $O(q \log n)$ памяти.

 1 struct segtree {
 2 	segtree* l = nullptr, r = nullptr;
 3 	int sum = 0;
 4 };
 5 
 6 segtree *root = new segtree();
 7 
 8 segtree * make() {
 9 	return new segtree();
10 }
11 
12 int getsum(segtree* v) {
13 	if (v == nullptr) return 0;
14 	return v->sum;
15 }
16 
17 void update(segtree* v, int tl, int tr, int pos) {
18 	if (tl + 1 == tr) {
19 		v->sum++;
20                 return;
21 	}
22 	if (v->l == nullptr) {
23 		v->l = make();
24 	}
25 	if (v->r == nullptr) {
26 		v->r = make();
27 	}
28 	int tm = (tl + tr) / 2;
29 	if (pos < tm) {
30 	        update(v->l, tl, tm, pos);
31 	}
32 	else {
33 		update(v->r, tm, tr, pos);
34 	}
35 	v->sum = getsum(v->l) + getsum(v->r);
36 	return nw;
37 }
38 
39 inline int get(segtree *v, int tl, int tr, int l, int r) {
40 	if (l >= tr || tl >= r || v == nullptr) {
41                  return 0;
42         }
43         if (l <= tl && tr <= r) {
44                   return v->sum;
45         }
46         int tm = (tl + tr) / 2;
47         return get(v->l, tl, tm, l, r) + get(v->r, tm, tr, l, r);
48 }

Use Cases

Используемая в статье техника полезна при работе с:

Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s [Категория:Структуры данных для запросов на отрезке]