Универсальное дерево отрезков

Vadym Gordiichuk

2019.02.07

Прежде всего, я хочу отблагодарить преподавателей Антоненка Александра (asantonenko@gmail.com), Максимова Артура и Мазурка Игоря. Думаю, если бы не их советы и лекции, а также отличное изложение учебного материала, реализованное мною универсальное дерево отрезков могло бы либо быть менее удобным для использования, либо попросту не существовало.

Примечание: для того, чтобы данная статья имела максимальную пользу для читателя, он должен обладать базовыми познаниями в языке программирования C++ и некоторое представление об асимптотике и математических записях.

Запись функции \(f\) в виде отображения из декартова произведения множеств в некоторое другое множество например записью \(f: A \times B \to C\) означает то, что функция \(f = f \left( x, y \right)\) принимает два аргумента \(x\) и \(y\), где \(x \in A\) (словесно: \(x\) из множества \(A\)), \(y \in B\), а результатом является элемент множества \(C\), то есть \(f \left( a, b \right) \in C\). Иными словами, под записями вида \(f: A \times B \to C\) читатель может понимать следующее: функция \(f\) определена таким образом, что для элемента \(a\) из множества \(A\) и для элемента \(b\) из множества \(B\) существует такой элемент \(c\) из множества \(C\), что \(f \left( a, b \right) = c\).

Вспомогательные материалы

Определение: Пусть \(G\) – непустое множество. Бинарная операция \(\circ\) на этом множестве (\(\circ: G \times G \to G\)) называется ассоциативной, если для любых элементов \(a\), \(b\) и \(c\) множества \(G\) выполнено условие:
\(\left( a \circ b \right)\) \(\circ\) \(c\) \(=\) \(a\) \(\circ\) \(\left( b \circ c \right)\)

\({\mathbb{N}}_0 = \mathbb{N} \cup \{ 0 \}\), где \(\mathbb{N}\) – множество натуральных чисел.

Задача множественных результатов и модификаций на отрезке

В программировании встречаются задачи следующего вида:
Пусть заданы \(G\) – некоторое непустое множество рассматриваемых операндов, \(\circ:\) \(G\) \(\times\) \(G\) \(\to\) \(G\) – некоторая ассоциативная бинарная операция на множестве \(G\), и \(M\) – непустое множество модификаторов, \(f: G \times M \to G\) – функция-модификатор элементов множества \(G\). Пусть в потоке входных данных заданы: числа \(n, m \in \mathbb{N}\); массив из \(n\) элементов \(a_{i}\), \(a_{i} \in G\), \(i = \overline{0, n-1}\) \(\left( a_{0}, a_{1}, \ldots, a_{n-2}, a_{n-1} \right)\).
После массива следует \(m\) запросов двух типов:

  1. Запрос вычисления результата: в потоке ввода даются два числа \(l\), \(r\), \(0 \le l \le r \le n-1\), \(l, r \in {\mathbb{N}}_0\). Вычислить результат операции \(\circ\) на отрезке \(\left[ l, r \right]\) – \(A_{\left[ l, r \right]}\), где \(A_{\left[ l, r \right]} = a_l \circ a_{l+1} \circ \ldots \circ a_{r-1} \circ a_r\), и вывести его в поток вывода;
  2. Запрос модификации отрезка: в потоке ввода даются два числа \(l, r\), \(0 \le l \le r \le n-1\), \(l, r \in {\mathbb{N}}_0\) и некое значение \(y\), \(y \in M\). модифицировать отрезок \(\left[ l, r \right]\), заменив значения элементов \(a_i\) на \(f \left( a_i, y \right)\), \(i = \overline{l, r}\).

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

  1. Модифицировать не весь отрезок, а только вершины, отвечающей за результат операции \(\circ\) на нём.
  2. Модификации накапливаются, и выполняются на меньших отрезках только тогда, когда подаются запросы на отрезки, которые были затронуты этими модификациями.

Объясню, почему используется именно ДОММ.

Зачастую начинающие программисты начинают решать задачи подобного рода так называемым “наивным способом”: модификации и вычисление результата заданной операции \(\circ\) на определённом отрезке проводятся циклом напрямую.
Псевдокод подобного решения:

Асимптотическая сложность модификации отрезка при такой реализации составляет в худших случаях \(O \left( n \cdot c_{f} \right)\), а сложность вычисления результата операции на отрезке – \(O \left( n \cdot c_{\circ} \right)\), где \(c_{f}\) – сложность выполнения модификации элемента массива функцией \(f\), \(c_{\circ}\) – сложность выполнения одной операции \(\circ\). Общая асимптотическая сложность программы при этом будет \(O \left( m \cdot n \cdot \left(c_{f}+c_{\circ}\right) \right)\), поскольку задача содержит \(m\) запросов.

Дерево отрезков для множественной модификации позволяет сократить расходы времени, и значительно улучшить общую асимптотику программы до \(O \left( \left( n + m \cdot \log_{2}{n} \right) \cdot \left( c_{f}+c_{\circ} \right) \right)\).

Безусловно, для каждой задачи существует своё решение. Однако, большинство задач содержат закономерности, которые позволяют так или иначе упростить их решение. Исходя из подобных рассуждений, я решил реализовать универсальное дерево отрезков для множественной модификации, поскольку намного проще использовать готовое решение под большинство разновидностей задач, чем для каждой задачи каждый раз переписывать его заново, но с небольшими отличиями. Оно может быть неидеальным для решения каждой задачи того вида, который приведён в начале данной статьи (к тому же могут существовать разновидности данной задачи, которые решаются вообще без использования данного дерева), однако быстрейшее выполнение задачи в момент её постановки (что наиболее часто встречается в олимпиадном программировании) компенсирует это. К тому же, в дальнейшем универсальное дерево отрезков может быть использовано в качестве шаблона и быть несколько видоизменено или оптимизировано специально под конкретную задачу.

Так или иначе, я приведу код универсального ДОММ, а также дополнительные условия, которые накладываются на задачу для применения данной структуры данных и инструкцию по использованию этой структуры. Прошу заметить, что Вам необязательно (хотя полезно) знать принципы работы ДОММ либо пытаться полностью понять написанный ниже код, чтобы решать задачи с помощью универсального ДОММ.

Код универсального ДОММ (на языке C++)

ДОММ: версия 1.2.0 (рекурсивная)

В этой версии дерева используется рекурсия. Тестирование показало, что оно работает (приблизительно) на 26% быстрее, чем та версия дерева, которая использует std::stack для избежания перегрузки системного стека. Лично я рекомендую использовать именно эту версию, однако для задач с чрезмерно (что врядли произойдёт) большим количеством элементов массива \(n\) оно может производить ошибки.

ДОММ: версия 1.2.0 (использующая стек)

В этой версии дерева используется структура данных std::stack. Рекомендуется использовать вместо рекурсивной версии только для избежания перегрузки системного стека (в задачах с чрезмерно большим количеством элементов массива \(n\)), поскольку рекурсивная реализация дерева работает (приблизительно) на 26% быстрее этой.

Условия применимости ДОММ

Должно быть определено расширенное множество модификаторов \(M_{2}\), удовлетворяющее условию:

  • если существует некоторый нейтральный модификатор \(e_{M} \in M\), который удовлетворяет условию \(\forall a \in G:\) \(f \left( a, e_{M} \right)\) \(=\) \(a\), то \(M_{2}\) \(=\) \(M\),
  • иначе должен быть определён элемент \(e_{M}\), который является нейтральным маркером (то есть формальным нейтральным модификатором) и удовлетворяет условию \(e_{M} \notin M\), и тогда \(M_{2}\) \(=\) \(M \cup \{ e_{M} \}\).

Для функции-модификатора \(f\):

  1. должна существовать комбинирующая функция \(C: M_{2} \times M \to M\), которая комбинирует накопленные модификаторы, и удовлетворяет условиям:
    • условие объединения: \(\forall a \in G\), \(\forall m_{1}, m_{2} \in M\): \(f \left( a, {C \left( m_{1}, m_{2} \right)} \right)\) \(=\) \(f \left( {f \left( a, m_{1} \right)}, m_{2} \right)\);
    • условие нейтрального модификатора/маркера: \(\forall m \in M\): \(C \left( e_{M}, m \right)\) \(=\) \(m\)
  2. должна существовать распределяющая функция \(K: M \times \mathbb{N} \to M\), которая распределяет модификатор, применяемый к целому отрезку определённой длины, и которая для отрезка \(\left[ l, r \right]\), к которому применяется модификатор \(m \in M\), где \(a_{l}\), \(a_{l+1}\), \(\ldots\), \(a_{r-1}\), \(a_{r}\) – модифицируемые элементы этого отрезка, и \(\delta = r – l + 1 \ge 1\) – количество этих элементов, удовлетворяет условию:
    \(f \left( {a_{l} \circ a_{l+1} \circ \ldots \circ a_{r-1} \circ a_{r}}, {K \left( m, \delta \right)} \right)\) \(=\) \(f \left( a_{l}, m \right) \circ f \left( a_{l+1}, m \right) \circ \ldots \circ f \left( a_{r-1}, m \right) \circ f \left( a_{r}, m \right)\)
  3. по распределяющей функции \(K\) должна быть определена расширенная функция-модификатор \(F: G \times M \times \mathbb{N} \to G\), которая модифицирует результат на отрезке \(\left[ l, r \right]\) с количеством элементов \(\delta = r – l + 1\):
    \(F \left( {a_{l} \circ a_{l+1} \circ \ldots \circ a_{r-1} \circ a_{r}}, m, \delta \right)\) \(=\) \(f \left( {a_{l} \circ a_{l+1} \circ \ldots \circ a_{r-1} \circ a_{r}}, {K \left( m, \delta \right)} \right)\).

    Примечание

    Хочу заметить, что для случая, когда модифицируется только один элемент с номером \(i\), то есть тогда, когда левый и правый концы модифицируемого отрезка совпадают \(l = r = i\), и \(\delta = 1\), расширенная функция-модификатор \(F\) по своему определению совпадает с исходной \(f\):
    \(F \left( a_{i}, m, \delta \right)\) \(=\) \(F \left( a_{i}, m, 1 \right)\) \(=\) \(f \left( a_i, m \right)\). Это делает ДОММ применимым даже для задач, в которых модифицируются не отрезки, а отдельные элементы массива (так называемые задачи единичной модификации).

Документация универсального ДОММ

Инструкция по использованию

  1. Скопировать код универсального ДОММ в программу, в которой планируется использование этой структуры данных, либо подключить её код из независимой библиотеки.
  2. Определить структуры данных с публичными конструкторами без аргументов, которые подходят на роль рассматриваемых операндов из множества \(G\) и на роль модификаторов множества \(M_{2}\):

    Замечание: в зависимости от задачи, используемые структуры/типы данных могут быть уже определены. Например, роль рассматриваемых элементов и модификаторов может играть стандартный тип данных int. Поэтому этот пункт в зависимости от задачи может быть необязательным.

  3. Описать заданную на множестве \(G\) операцию \(\circ\), расширенную функцию-модификатор \(F\) и комбинирующую функцию \(C\):

  4. Определить объект типа “дерево отрезков”, передав ему в качестве параметров для шаблона типы операндов и модификаторов:

  5. Сконструировать дерево отрезков одним из методов:
    • метод read:
      Описать функцию-препроцессор (которая, например, считывает данные непосредственно из входного потока, обрабатывает их и создаёт на их основании элементы массива из условия), которая будет поочерёдно создавать элементы массива из задачи от элемента с номером \(0\) до элемента с номером \(n-1\).

      На основании функции-препроцессора и известного количества элементов \(n\) построить дерево отрезков, вызвав метод read, передав ему в качестве аргументов соответственно количество элементов \(n\), функцию-препроцессор, операцию \(\circ\), расширенную функцию-модификатор \(F\), комбинирующую функцию \(C\) и нейтральный модификатор/маркер \(e_{M}\):

    • метод construct:
      Определить некоторый непустой массива элементов \(G\) с адресом начала begin и адресом конца end (то есть все элементы \(a_{i}\) должны находится в полуинтервале \(\left[ {begin}, {end} \right)\), и если массив имеет длину \(n\), то end \(=\) begin+n)
      Построить дерево отрезков, вызвав метод construct_from, передав ему в качестве аргументов соответственно адрес начала массива, адрес конца массива, операцию \(\circ\), расширенную функцию-модификатор \(F\), комбинирующую функцию \(C\) и нейтральный модификатор/маркер \(e_{M}\):

      Сначала структура данных скопирует исходный массив, а затем на его основании построит дерево отрезков. Этот метод полезен, если требуется сохранить исходный массив, и использовать его в дальнейшем.

  6. Выполнять запросы на результат и на модификацию следующим образом:
    1. Определить левый и правый конец рассматриваемого отрезка:

    2. Определить тип запроса к дереву отрезков, и вызвать соответствующий запросу метод дерева:
      1. для запросов модификации отрезка:
        определить некоторый модификатор m

        и вызвать метод дерева отрезков modify, передав ему в качестве аргументов левый конец модифицируемого отрезка, правый конец модифицируемого отрезка и модификатор m:

      2. для запросов результата операции \(\circ\) на отрезке вызвать метод result, передав ему в качестве аргументов левый и правый концы модифицируемого отрезка:

Методы класса

Обозначения:

  • \(n\) – количество элементов исходного массива.
  • \(m_{G}\) – количество памяти, занимаемое элементом множества \(G\)
  • \(m_{M}\) – количество памяти, занимаемое модификатором из множества \(M_{2}\)
  • \(c_{F}\) – сложность модификации элемента множества \(G\) расширенной функцией-модификатором \(F\).
  • \(c_{C}\) – сложность комбинирующей функции \(C\).
  • \(c_{\circ}\) – сложность выполнения операции \(\circ\).
  • TYPE – тип операндов множества \(G\).
  • MODIFIER_TYPE – тип модификаторов множества \(M_{2}\).
Название метода Описание метода
construct Тип возвращаемого значения: void

Аргументы
  1. const TYPE *begin – адрес начала копируемого массива;
  2. const TYPE *end – адрес конца копируемого массива;
  3. TYPE f(const TYPE&, const TYPE&) – операция \(\circ\) множества \(G\);
  4. TYPE modifier_function(const TYPE&, const MODIFIER_TYPE&, const size_t&) – расширенная функция-модификатор \(F\);
  5. MODIFIER_TYPE modification_combine(const MODIFIER_TYPE&, const MODIFIER_TYPE&) – комбинирующая функция \(C\);
  6. const MODIFIER_TYPE& new_neutral_modifier – нейтральный модификатор/маркер \(e_{M}\).

Использование времени: \(O \left( {c_{\circ}} \cdot n \right)\); \(2 \cdot n + {\log_{2}{n}} + n \cdot {c_{\circ}}\) в худшем случае, \(2 \cdot n + n \cdot c_{\circ}\) в лучшем.
Использование памяти: \(O \left( n \cdot \left( m_{G} + m_{M} \right) \right)\); \({\log_{2}{n}} + 2 \cdot n \cdot m_{G} + n \cdot m_{M}\) в худшем случае, \(2 \cdot n \cdot m_{G} + n \cdot m_{M}\) в лучшем.
Описание: строит дерево отрезков на основании данного массива, копируя его элементы непосредственно в дерево.

read Тип возвращаемого значения: void

Аргументы
  1. const size_t& amount_of_elements – количество элементов множества \(G\);
  2. TYPE preprocessing_function() – функция-препроцессор, создающая рассматриваемые элементы;
  3. TYPE f(const TYPE&, const TYPE&) – операция \(\circ\) множества \(G\);
  4. TYPE modifier_function(const TYPE&, const MODIFIER_TYPE&, const size_t&) – расширенная функция-модификатор \(F\);
  5. MODIFIER_TYPE modification_combine(const MODIFIER_TYPE&, const MODIFIER_TYPE&) – комбинирующая функция \(C\);
  6. const MODIFIER_TYPE& new_neutral_modifier – нейтральный модификатор/маркер \(e_{M}\).

Использование времени: \(O \left( {c_{\circ}} \cdot n \right)\); \(2 \cdot n + {\log_{2}{n}} + n \cdot {c_{\circ}}\) в худшем случае, \(2 \cdot n + n \cdot c_{\circ}\) в лучшем.
Использование памяти: \(O \left( n \cdot \left( m_{G} + m_{M} \right) \right)\); \({\log_{2}{n}} + 2 \cdot n \cdot m_{G} + n \cdot m_{M}\) в худшем случае, \(2 \cdot n \cdot m_{G} + n \cdot m_{M}\) в лучшем.
Описание: строит дерево на основании заданной функции-препроцессора, вызывая её \(n\) раз и последовательно записывая возвращаемые ей элементы множества \(G\).

modify Тип возвращаемого значения: void

Аргументы
  1. const size_t& i – индекс модифицируемого элемента;
  2. const MODIFIER_TYPE& modifier – модификатор из множества \(M\).

Использование времени: \(O \left( \left( c_{F} + c_{C} + c_{\circ} \right) \cdot \log_{2}{n} \right)\); \(\left( c_{F} + c_{C} + c_{\circ} \right) \cdot 2 \cdot \log_{2}{n}\) в худшем случае, \(\left( c_{F} + c_{C} + c_{\circ} \right) \cdot \log_{2}{n}\) в лучшем.
Использование памяти: \(O \left( \left( m_{G} + m_{M} \right) \cdot \log_{2}{n} \right)\); \(\left( m_{G} + m_{M} \right) \cdot 2 \cdot \log_{2}{n}\) в худшем случае, \(\left( m_{G} + m_{M} \right) \cdot \log_{2}{n}\) в лучшем.
Описание: модифицирует элемент с заданным индексом данным модификатором.

modify Тип возвращаемого значения: void

Аргументы
  1. const size_t& l – индекс левого конца модифицируемого отрезка;
  2. const size_t& r – индекс правого конца модифицируемого отрезка;
  3. const MODIFIER_TYPE& modifier – модификатор из множества \(M\).

Использование времени: \(O \left( \left( c_{F} + c_{C} + c_{\circ} \right) \cdot \log_{2}{n} \right)\); \(\left( c_{F} + c_{C} + c_{\circ} \right) \cdot 2 \cdot \log_{2}{n}\) в худшем случае, \(\left( c_{F} + c_{C} + c_{\circ} \right) \cdot \log_{2}{n}\) в лучшем.
Использование памяти: \(O \left( \left( m_{G} + m_{M} \right) \cdot \log_{2}{n} \right)\); \(\left( m_{G} + m_{M} \right) \cdot 2 \cdot \log_{2}{n}\) в худшем случае, \(\left( m_{G} + m_{M} \right) \cdot \log_{2}{n}\) в лучшем.
Описание: Модифицирует отрезок с заданными границами данным модификатором.

result Тип возвращаемого значения: TYPE

Аргументы
  1. const size_t& l – индекс левого конца отрезка;
  2. const size_t& r – индекс правого конца отрезка;

Использование времени: \(O \left( \left( c_{F} + c_{C} + c_{\circ} \right) \cdot \log_{2}{n} \right)\); \(\left( c_{F} + c_{C} + c_{\circ} \right) \cdot 2 \cdot \log_{2}{n}\) в худшем случае, \(\left( c_{F} + c_{C} + c_{\circ} \right) \cdot \log_{2}{n}\) в лучшем.
Использование памяти: \(O \left( \left( m_{G} + m_{M} \right) \cdot \log_{2}{n} \right)\); \(\left( m_{G} + m_{M} \right) \cdot 2 \cdot \log_{2}{n}\) в худшем случае, \(\left( m_{G} + m_{M} \right) \cdot \log_{2}{n}\) в лучшем.
Описание: возвращает результат операции \(\circ\) на заданном отрезке.