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

Предисловие и постановка задачи


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

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

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

Итак, задача.

Есть поле NxM, необходимо выполнять два типа запросов:
  1. Изменить значения ячеек с координатами, удовлетворяющими условиям x1<=x<=x2, y1<=y<=y2 на val
  2. Вычислить значение некой функции (ассоциативной бинарной операции) от ячеек с координатами, удовлетворяющими условиям x1<=x<=x2, y1<=y<=y2

Здесь я опишу реализацию решения задачи, где функция — сумма. Сразу скажу, что до этого решения я доходил сам (в течении около 15 часов), так что не исключаю существования более простого, и даже рад буду его послушать.

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



image

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

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

Назовем сектором некоторый прямоугольник, образуемый ячейками x1<=x<=x2, y1<=y<=y2. Тогда каждая вершина вложенного поддерева отвечает за некий сектор.

В каждом узле «вложенного» дерева мы будем хранить четыре параметра:
  • 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<=x0_1 AND x0_2<=x2 AND y1<=y0_1 AND y0_2<=y2. т. е. Достаточно собрать множество X x-овых, Y для y-овых, а потом перебрать все пары из XxY.
Ну а чтобы собрать эти самые списки, необходимо пройти по вершинам, как в случае с запросом на одномерно дереве.

Рассматривая же конкретную пару (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;

С add, думаю, все понятно (см одномерный случай).

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

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

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


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

xvl = max(xl, x1), xvr = min(xr, x2), yvl = max(yl, y1), yvr = min(yr, y2)
  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. Спасибо всем за внимание, надеюсь эта статья будет кому-нибудь полезна.
Share post

Comments 11

    0
    а спроецировать на sql?
    я много видел таких статей и сам занимался этими деревьями.
    у Вас, сухой пересказ теории по моему разумению.
      0
      На SQL? Можете попробовать, но данная статья писалась в первую очередь для тех, кто интересуется олимпиадным программированием.

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

          Ссылка та же самая)
            0
            Да, вы правы, пост прочитал, а вот по ссылку не заглянул)))
        0
        Отлично подойдёт для вот этого конкурса. Только на сколько я понимаю памяти понадобится много.
          0
          Не, не думаю. Там задача формулируется что надо найти максимальную сумму на уже данной матрице, а дерево отрезков используется именно когда помимо запросов суммы нам нужно обрабатывать запросы модификации
            0
            Насколько могу судить по личному опыту, намного чаще приходится работать с набором сильно разреженных точек на плоскости, нежели с фиксированной матрицей.

            Думаю было бы полезно добавить обобщение решения задачи на случай точек на плоскости, а так конечно все по существу.
              0
              М… не могли бы вы скинуть пример такой задачи? Просто кроме той задачи, ссылку на которую я дал в конце статьи я не видел задач на эту структуру.
                0
                Я пришлю вам на днях пару ссылок, сразу и не вспомню где именно я сталкивался с несколькими подобными.
                  0
                  Буду весьма благодарен, а если еще и разберусь с тем материалом, то можно еще статейку написать, в дополнение к этой:)

            Only users with full accounts can post comments. Log in, please.