Двумерное дерево отрезков визуализация

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

В случае, если наша задача задана в 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 > 

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

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

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

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

Источник

Двумерное дерево отрезков (с групповой модификацией элементов)

Думаю, многие читатели этого сайта слышали о такой полезной структуре, как дерево отрезков. А если нет, то о нем в интернете можно отыскать множество интересного материала (здесь, статьи на Хабре: раз и два, google, наконец).
Здесь я разберу обобщение дерева отрезков на двумерный случай, причем (в отличие от этой статьи) рассмотрю реализацию дерева именно с поддержкой групповой модификации элементов.

Вообще, во многих случаях можно обойтись без дерева отрезков вообще, например воспользоваться деревом Фенвика — пишется гораздо легче дерева отрезков, имеет меньшую константу, очевидно распространяется на большие размерности. Но имеет как минимум два минуса: реализует лишь обратимые операции (чтобы заставить его считать минимум/максимум придется изрядно извратится, причем даже тогда оно не будет давать полной свободы действия (в модификации с максимумом — только увеличивать значение, не уменьшать, с минимумом — наоборот)) и не поддерживает групповую модификацию элементов.

Хорошая SQRT-декомпозици с хитрым подбором длины блока также иногда поможет, но все же с мощью дерева отрезков не сравнить.

Структура дерева

По структуре двумерное дерево отрезков представляет дерево отрезков из деревьев отрезков (в каждом узле дерева глубины X_DEPTH есть «вложенное» дерево глубины Y_DEPTH). Здесь и далее глубина дерева — двоичный логарифм от количества элементов, которое оно может вместить. Например, на рисунке изображено дерево глубины 1, в каждом узле которого содержится дерево глубины 2. Такое дерево может обрабатывать запросы вида [x1;x2]⊆[0;1], [y1;y2]⊆[0;3].

Занумеруем вершины этих деревьев (как внешнего, так и всех вложенных) как обычные одномерные деревья.
Тогда каждая вершина вложенного будет характеризоваться координатой [x][y], x — номер вершины внешнего дерева, в котором она находится, y — внутреннего.

• add — величина, на которую нужно увеличить результат при запросе суммы на вложенных секторах (потомках по x-й и y-й координатам)
• add_x — величина, на которую нужно увеличить результат при запросе суммы на не полностью вложенных отрезках (потомках по y-й координате, но с той же x-й)
• add_y — величина, на которую нужно увеличить результат при запросе суммы на не полностью вложенных отрезках (потомках по x-й координате, но с той же y-й)
• value — сумма в поддереве вершины (не считая перечисленных выше добавлений)

Препроцессинг операций

Когда мы выполняем операцию модификации, как и в одномерном случае, мы будем изменять значения лишь определенного для данного сектора списка вершин. При суммировании на том же секторе мы будем обращаться к тем же вершинам.

Если мы изменим значение вершины [x0][y0], отвечающую за сектор [x0_1;x0_2][y0_1;y0_2], то не трудно понять, что все сектора, включающие этот сектор могут быть найдены как пары (x;y): x1 Ну а чтобы собрать эти самые списки, необходимо пройти по вершинам, как в случае с запросом на одномерно дереве.

Рассматривая же конкретную пару (x;y) можно легко вычислить xl, xr, yl, yr — границы секотра текущей вершины, а также xc и yc — количества элементов в пересечениях по x-овой и y-овой осях.

Операция модификации

1. Если запрос полностью включает в себя сектор текущей вершины, то нужно добавить в add вершины изменение val (ко всем потомкам и по x-й и по y-й нужно прибавить val):
   add +=val;
2. Если запрос включает текущий сектор лишь по x-й кординате, изменяем add_y:
   add_y += val*xc;
3. Если запрос включает текущий сектор лишь по y-й кординате, изменяем add_x:
   add_x += val*yc;
4. Если запрос не включает сектор вообще:
   value += val*xc*yc;

Когда запрос включает текущий сектор по y-й координате, значит по y-й могут быть потомки, которые не будут затронуты в данном запросе, но будут при запросах суммы в дальнейшем. Потому мы и увеличиваем add_x.
Аналогично и с add_y.

И, наконец, если ни одно из трех предыдущих условий не соблюдено, значит сред прямых потомков данной вершины один изменится, а второй нет. Следовательно, данное изменение нужно учесть, но не распространять дальше. Увеличиваем value.

Операция суммирования

Обозначим за res результат запроса, который мы и будем вычислять. Дополнительно к препроцессингу, вычислим границы той части запроса, которую мы ищем в данной вершине (границы искомой части):

1. Нам необходимо прибавить ко всем ячейкам запроса, лежащих в текущем секторе add текущей вершины:
   res += add*xc*yc;
2. Если искомая часть равна сектору вершины по x-овому диапозону:
   res += add_x*yc;
3. Если искомая часть равна сектору вершины по y-овому диапозону:
   res += add_y*xc;
4. Если сектор текущей вершины целиком лежит в запросе (ниже мы спускаться не будем):
   res += value;

Асимптотика

Как видно из описания, данное решение будет работать за O(N*X_DEPTH*Y_DEPTH), где N — количество запросов.

Реализация

Реализацию этого решения можете посмотреть по ссылке http://dl.dropbox.com/u/3693476/articles/segtree2d/segtree2d.cpp (файл-решение задачи Ферма, D из файла http://dl.dropbox.com/u/3693476/articles/segtree2d/problems01.pdf). Если хотите получить тесты к этой задаче, чтобы отладить своё решение, напишите свою просьбу на мой почтовый ящик george.agapov@gmail.com.

P.S. Спасибо всем за внимание, надеюсь эта статья будет кому-нибудь полезна.

Источник

Двумерное дерево отрезков (с групповой модификацией элементов)

Думаю, многие читатели этого сайта слышали о такой полезной структуре, как дерево отрезков. А если нет, то о нем в интернете можно отыскать множество интересного материала (здесь, статьи на Хабре: раз и два, google, наконец).
Здесь я разберу обобщение дерева отрезков на двумерный случай, причем (в отличие от этой статьи) рассмотрю реализацию дерева именно с поддержкой групповой модификации элементов.

Вообще, во многих случаях можно обойтись без дерева отрезков вообще, например воспользоваться деревом Фенвика — пишется гораздо легче дерева отрезков, имеет меньшую константу, очевидно распространяется на большие размерности. Но имеет как минимум два минуса: реализует лишь обратимые операции (чтобы заставить его считать минимум/максимум придется изрядно извратится, причем даже тогда оно не будет давать полной свободы действия (в модификации с максимумом — только увеличивать значение, не уменьшать, с минимумом — наоборот)) и не поддерживает групповую модификацию элементов.

Хорошая SQRT-декомпозици с хитрым подбором длины блока также иногда поможет, но все же с мощью дерева отрезков не сравнить.

Структура дерева

По структуре двумерное дерево отрезков представляет дерево отрезков из деревьев отрезков (в каждом узле дерева глубины X_DEPTH есть «вложенное» дерево глубины Y_DEPTH). Здесь и далее глубина дерева — двоичный логарифм от количества элементов, которое оно может вместить. Например, на рисунке изображено дерево глубины 1, в каждом узле которого содержится дерево глубины 2. Такое дерево может обрабатывать запросы вида [x1;x2]⊆[0;1], [y1;y2]⊆[0;3].

Занумеруем вершины этих деревьев (как внешнего, так и всех вложенных) как обычные одномерные деревья.
Тогда каждая вершина вложенного будет характеризоваться координатой [x][y], x — номер вершины внешнего дерева, в котором она находится, y — внутреннего.

• add — величина, на которую нужно увеличить результат при запросе суммы на вложенных секторах (потомках по x-й и y-й координатам)
• add_x — величина, на которую нужно увеличить результат при запросе суммы на не полностью вложенных отрезках (потомках по y-й координате, но с той же x-й)
• add_y — величина, на которую нужно увеличить результат при запросе суммы на не полностью вложенных отрезках (потомках по x-й координате, но с той же y-й)
• value — сумма в поддереве вершины (не считая перечисленных выше добавлений)

Препроцессинг операций

Когда мы выполняем операцию модификации, как и в одномерном случае, мы будем изменять значения лишь определенного для данного сектора списка вершин. При суммировании на том же секторе мы будем обращаться к тем же вершинам.

Если мы изменим значение вершины [x0][y0], отвечающую за сектор [x0_1;x0_2][y0_1;y0_2], то не трудно понять, что все сектора, включающие этот сектор могут быть найдены как пары (x;y): x1 Ну а чтобы собрать эти самые списки, необходимо пройти по вершинам, как в случае с запросом на одномерно дереве.

Рассматривая же конкретную пару (x;y) можно легко вычислить xl, xr, yl, yr — границы секотра текущей вершины, а также xc и yc — количества элементов в пересечениях по x-овой и y-овой осях.

Операция модификации

1. Если запрос полностью включает в себя сектор текущей вершины, то нужно добавить в add вершины изменение val (ко всем потомкам и по x-й и по y-й нужно прибавить val):
   add +=val;
2. Если запрос включает текущий сектор лишь по x-й кординате, изменяем add_y:
   add_y += val*xc;
3. Если запрос включает текущий сектор лишь по y-й кординате, изменяем add_x:
   add_x += val*yc;
4. Если запрос не включает сектор вообще:
   value += val*xc*yc;

Когда запрос включает текущий сектор по y-й координате, значит по y-й могут быть потомки, которые не будут затронуты в данном запросе, но будут при запросах суммы в дальнейшем. Потому мы и увеличиваем add_x.
Аналогично и с add_y.

И, наконец, если ни одно из трех предыдущих условий не соблюдено, значит сред прямых потомков данной вершины один изменится, а второй нет. Следовательно, данное изменение нужно учесть, но не распространять дальше. Увеличиваем value.

Операция суммирования

Обозначим за res результат запроса, который мы и будем вычислять. Дополнительно к препроцессингу, вычислим границы той части запроса, которую мы ищем в данной вершине (границы искомой части):

1. Нам необходимо прибавить ко всем ячейкам запроса, лежащих в текущем секторе add текущей вершины:
   res += add*xc*yc;
2. Если искомая часть равна сектору вершины по x-овому диапозону:
   res += add_x*yc;
3. Если искомая часть равна сектору вершины по y-овому диапозону:
   res += add_y*xc;
4. Если сектор текущей вершины целиком лежит в запросе (ниже мы спускаться не будем):
   res += value;

Асимптотика

Как видно из описания, данное решение будет работать за O(N*X_DEPTH*Y_DEPTH), где N — количество запросов.

Реализация

Реализацию этого решения можете посмотреть по ссылке http://dl.dropbox.com/u/3693476/articles/segtree2d/segtree2d.cpp (файл-решение задачи Ферма, D из файла http://dl.dropbox.com/u/3693476/articles/segtree2d/problems01.pdf). Если хотите получить тесты к этой задаче, чтобы отладить своё решение, напишите свою просьбу на мой почтовый ящик george.agapov@gmail.com.

P.S. Спасибо всем за внимание, надеюсь эта статья будет кому-нибудь полезна.

Источник