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

В случае, если наша задача задана в 2d пространстве, мы можем делать много странных вещей со структурами. По сути, мы хотим комбинировать их между собой и использовать в каждый момент времени ту, которая будет эффективнее и удобнее.

Как считать время и память для таких структур? Пусть у нас есть структуры $A, B$, с затратами на время и память $time_A, time_B, memory_A, memory_B$. Тогда общая сложность по времени и памяти для структуры А, которая хранит в каждой своей ячейке структуру B — это $O(time_A \cdot time_B), O(memory_A \cdot memory_B)$.

Двумерное дерево отрезков

В вершине дерева отрезков можно хранить не только число, но еще и другое дерево отрезков. Обобщать это на многомерные случаи не очень приятно, но применимо к 2д задачам это выглядит примерно так:

 1 int get_inside(int v, int tl, int tr, int l, int r, segtree_outside &root) {
 2 	if (tl >= r || l >= tr) {
 3 		return INT32_MAX;
 4 	}
 5 	if (l <= tl && tr <= r) {
 6 		return root.t[v].val;
 7 	}
 8 	int tm = (tl + tr) / 2;
 9 	return min(get_inside(2 * v, tl, tm, l, r, root), get_inside(2 * v + 1, tm, tr, l, r, root));
10 }
11 
12 int get_outside(int v, int tl, int tr, int l, int r, int a, int b) {
13 	if (tl >= r || l >= tr) {
14 		return INT32_MAX;
15 	}
16 	if (l <= tl && tr <= r) {
17 		return get_inside(1, 0, n - 1, a, b, t[v]);
18 	}
19 	int tm = (tl + tr) / 2;
20 	return min(get_outside(2 * v, tl, tm, l, r, a, b), get_outside(2 * v + 1, tm, tr, l, r, a, b));
21 }

Dynamic merge sort tree

Если мы хотели в каждой вершине дерева отрезков поддерживать отсортированный подотрезок массива, а также делать запросы на изменение значений, то можно написать что-то типа merge sort tree, но в каждой вершине хранить декартово дерево, а не массив.

Фенвик

В большом числе страшных двумерных структур есть возможность реализовать внешнюю структуру через [дерево Фенвика]. Такой подход сильно упростит код для задачи, а еще сильно ускорит его по времени. К примеру, для dynamic merge sort tree мы вполне могли обойтись Фенвиком декартачей. Согласитесь, что писать такой код куда проще.

---

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

По всем вопросам пишите в telegram @kik0s