Двумерные структуры данных
В случае, если наша задача задана в 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