Динамические структуры данных: различия между версиями
KiKoS (обсуждение | вклад) (Новая страница: «Иногда в задачах требуется построить структуру данных на массиве очень большого размер...») |
KiKoS (обсуждение | вклад) м (code + category) |
||
Строка 7: | Строка 7: | ||
Сделаем в дереве отрезков ряд изменений. Во-первых, напишем его на структурах и указателях. Каждая вершина дерева отрезков — это объект, который хранит указатели на своего левого и правого сына. Давайте решать эту задачу так, как мы решали бы ее обычным деревом отрезков, но <b>не вызовем</b> операцию построения. То есть изначально наше дерево отрезков — это корень. Создавать вершины мы будем в операциях обновления, если вершина еще не была создана (похожим на [отложенные операции] образом). При get-запросе считаем, что если вершина не создана, то сумма в ней 0 (логично ведь). Тогда за один запрос мы создадим $O(\log n)$ вершин, суммарно все будет работать за $O(q \log n)$ времени и $O(q \log n)$ памяти. | Сделаем в дереве отрезков ряд изменений. Во-первых, напишем его на структурах и указателях. Каждая вершина дерева отрезков — это объект, который хранит указатели на своего левого и правого сына. Давайте решать эту задачу так, как мы решали бы ее обычным деревом отрезков, но <b>не вызовем</b> операцию построения. То есть изначально наше дерево отрезков — это корень. Создавать вершины мы будем в операциях обновления, если вершина еще не была создана (похожим на [отложенные операции] образом). При get-запросе считаем, что если вершина не создана, то сумма в ней 0 (логично ведь). Тогда за один запрос мы создадим $O(\log n)$ вершин, суммарно все будет работать за $O(q \log n)$ времени и $O(q \log n)$ памяти. | ||
− | + | <syntaxhighlight lang='c++' line='line'> | |
+ | struct segtree { | ||
+ | segtree* l = nullptr, r = nullptr; | ||
+ | int sum = 0; | ||
+ | }; | ||
+ | segtree *root = new segtree(); | ||
+ | |||
+ | segtree * make() { | ||
+ | return new segtree(); | ||
+ | } | ||
+ | |||
+ | int getsum(segtree* v) { | ||
+ | if (v == nullptr) return 0; | ||
+ | return v->sum; | ||
+ | } | ||
+ | |||
+ | void update(segtree* v, int tl, int tr, int pos) { | ||
+ | if (tl + 1 == tr) { | ||
+ | v->sum++; | ||
+ | return; | ||
+ | } | ||
+ | if (v->l == nullptr) { | ||
+ | v->l = make(); | ||
+ | } | ||
+ | if (v->r == nullptr) { | ||
+ | v->r = make(); | ||
+ | } | ||
+ | int tm = (tl + tr) / 2; | ||
+ | if (pos < tm) { | ||
+ | update(v->l, tl, tm, pos); | ||
+ | } | ||
+ | else { | ||
+ | update(v->r, tm, tr, pos); | ||
+ | } | ||
+ | v->sum = getsum(v->l) + getsum(v->r); | ||
+ | return nw; | ||
+ | } | ||
+ | |||
+ | inline int get(segtree *v, int tl, int tr, int l, int r) { | ||
+ | if (l >= tr || tl >= r || v == nullptr) { | ||
+ | return 0; | ||
+ | } | ||
+ | if (l <= tl && tr <= r) { | ||
+ | return v->sum; | ||
+ | } | ||
+ | int tm = (tl + tr) / 2; | ||
+ | return get(v->l, tl, tm, l, r) + get(v->r, tm, tr, l, r); | ||
+ | } | ||
+ | </syntaxhighlight> | ||
====Use Cases==== | ====Use Cases==== | ||
Используемая в статье техника полезна при работе с: | Используемая в статье техника полезна при работе с: | ||
* [[Дерево отрезков|деревом отрезков]] | * [[Дерево отрезков|деревом отрезков]] | ||
* [[Li Chao Tree| деревом Ли Шао]] | * [[Li Chao Tree| деревом Ли Шао]] | ||
+ | {{Автор|Константин Амеличев|kik0s}} | ||
+ | [Категория:Структуры данных для запросов на отрезке] |
Текущая версия на 17:49, 18 сентября 2019
Иногда в задачах требуется построить структуру данных на массиве очень большого размера (таком, что он не помещается в память). При этом известно, что количество запросов к структуре невелико. Типичная задача: Дан массив размером $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 [Категория:Структуры данных для запросов на отрезке]