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

В случае, если наша задача задана в 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д задачам это выглядит примерно так:

<stylehighlight lang='c++' line='line'> int get_inside(int v, int tl, int tr, int l, int r, segtree_outside &root) { if (tl >= r || l >= tr) { return INT32_MAX; } if (l <= tl && tr <= r) { return root.t[v].val; } int tm = (tl + tr) / 2; return min(get_inside(2 * v, tl, tm, l, r, root), get_inside(2 * v + 1, tm, tr, l, r, root)); }

int get_outside(int v, int tl, int tr, int l, int r, int a, int b) { if (tl >= r || l >= tr) { return INT32_MAX; } if (l <= tl && tr <= r) { return get_inside(1, 0, n - 1, a, b, t[v]); } int tm = (tl + tr) / 2; return min(get_outside(2 * v, tl, tm, l, r, a, b), get_outside(2 * v + 1, tm, tr, l, r, a, b)); } </stylehighlight>

Dynamic merge sort tree

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

Фенвик

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