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

Vadym Gordiichuk

Эта статья, по сути, является дополнением к статье об универсальном дереве отрезков (которая далее по тексту будет упоминаться как Базовая Статья). Здесь будет приведён пример, как использовать универсальное дерево отрезков для задач множественной модификации.

Итак, в качестве примера для решения возьмём следующую задачу:

задача №2939 сайта www.e-olymp.com

Дима и массив

Мама подарила мальчику Диме массив длины \(n\). Массив этот не простой, а особенный. Дима может выбрать три числа – \(i\), \(j\) и \(d\) (\(1 \le i \le j \le n\), \(-1000 \le d \le 1000\)), и все элементы с индексами от \(i\) до \(j\) магически становятся равными \(d\). Дима играет со своим массивом, а мама время от времени задает ему вопросы – какова сумма всех чисел в массиве с индексами от \(f\) до \(t\)? Дима легко справился с этими вопросами, сможете ли Вы?

Входные данные

В первой строке находятся два целых числа \(n\) и \(q\) (\(1 \le n \le 5 \cdot 10^5\), \(1 \le q \le 10^5\)) – количество элементов в массиве и суммарное количество операций и запросов соответственно. В следующей строке дано \(n\) чисел \(a_1\), \(a_2\), \(\ldots\), \(a_n\) (\(-1000 \le a_i \le 1000\)) – начальное состояние массива. В следующих \(q\) строках заданы операции и запросы. Первый символ в строке может быть = или ?. Если строка начинается с =, то это операция присваивания. Далее следуют \(i\), \(j\) и \(d\), ограничения на которые заданы выше. Если строка начинается с ?, то это запрос. Далее следуют числа \(f\) и \(t\) (\(1 \le f, t \le n\)).

Выходные данные

Для каждого запроса выведите сумму чисел в массиве с индексами от \(f\) до \(t\), по одному результату в строке.

Прежде всего, я хочу заметить, что Дима – очень быстрый мальчик. Согласно условию, он может работать даже с массивом, в котором 500000 элементов! Скорее всего, на самом деле Дима – робот с довольно быстрым процессором, потому что обычный человек (даже достаточно быстрый, чтобы выполнять запросы = и ?) не способен удержать такой массив даже на бумаге, а тем более в голове. Хотя, согласно условию, массив, который подарила Диме мама – магический, а в науке “магия” является вполне приемлемым объяснением! 😀
Конечно, это была шутка, которую нам оставили авторы задачи. А теперь приступим к решению.

Решение задачи

1. Выявление формальной модели

Для начала построим сугубо математическую модель, а затем выполним её корректировку для написания максимально соответствующего ей кода.

Первое, что нам предстоит сделать – это подогнать задачу под общий шаблон задач из Базовой Статьи:

Пусть заданы \(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{1, n}\) \(\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}\).

Первое, что мы заметим – отличие решаемой задачи от шаблона: в решаемой задаче элементы массива нумеруются не с \(0\) по \(n-1\), а с \(1\) по \(n\), однако на основную математическую модель это отличие не влияет.

Итак, как видно из условия задачи, можно выделить элементы шаблона:

  1. Множество \(G\): в данной задаче, роль множества \(G\) может играть множество целых чисел \(\mathbb{Z}\), поскольку в массив из условия содержит целые числа \(-1000 \le a_i \le 1000\), \(i = \overline{0, n-1}\).
  2. Ассоциативная операция \(\circ\) на множестве \(G\): роль этой операции играет сложение \(+\), поскольку в задаче необходимо вычислять суммы на отрезках.
  3. Множество модификаторов \(M\) и функция-модификатор \(f\): по условию задачи, над элементами массива выполняется операция замены: “Дима может выбрать три числа – \(i\), \(j\) и \(d\) (\(1 \le i \le j \le n\), \(-1000 \le d \le 1000\)), и все элементы с индексами от \(i\) до \(j\) магически становятся равными \(d\)“. Поскольку в массиве производится замена одних чисел на другие, роль множества \(M\) тоже может быть выполнена множеством целых чисел \(\{-1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000\}\).
    Теперь, поскольку известны множества \(G\) и \(M\), можно определить функцию-модификатор \(f\), которая модифицирует одно число, заменяя его на другое:
    \(\forall g \in G\), \(\forall m \in M\): \(f \left( g, m \right) = m\).

Получившиеся элементы модели задачи:
\(G\) \(=\) \(\mathbb{Z}\)
\(\circ\) \(=\) \(+\)
\(M\) \(=\) \(\{-1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000\}\)
\(\forall g \in G\), \(\forall m \in M\): \(f \left( g, m \right) = m\)

Внимательный читатель задаст вопрос, почему множество \(G\) не было определено как множество \(\{-1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000\}\), поскольку в условии задачи элементы массива являются именно элементами множества \(\{-1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000\}\). Всё дело в том, что определение множества \(G\) зависит так же и от определённой на нём операции – если бы множество \(G\) было бы определено как множество \(\{-1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000\}\), оно не содержало бы результатов сложения элементов этого множества. Т.е., например, множество \(G\) не содержало бы элемента \(n \cdot 1000\), который может быть частным случаем суммы всех элементов на заданном массиве. Но, на самом деле, набирая этот текст, я зацепил тему “Философия взаимосвязей математики и программирования”, поэтому давайте продолжим.

2. Проверка условий применимости универсального дерева отрезков

Собственно, вот сами условия из Базовой Статьи:

Должно быть определено расширенное множество модификаторов \(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)\).

Множество \(M_2\)

Легко показать, что нейтральный модификатор \(e_M\) попросту не существует во множестве \(M\). Это следует из определения функции-модификатора \(f\):
\(\forall g \in G\), \(\forall m \in M\): \(f \left( g, m \right) = m\)
Из этого определения следует, что \(\forall g \in G\) \(f \left( g, e_M \right) = e_M\), и условие нейтрального модификатора \(\forall g \in G\) \(f \left( g, e_{M} \right) = g\) не может быть выполнено.

Итак, поскольку нейтральный модификатор не существует, требуется определение нейтрального маркера \(e_M\), который удовлетворяет единственному условию – \(e_M \notin M\). Итак, пусть, например, \(e_M = 1001\).
Тогда \(M_2\) \(=\) \(M \cup \{ 1001 \}\) \(=\) \(\{ -1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000 \}\) \(\cup\) \(\{ 1001 \}\) \(=\) \(\{ -1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000, 1001 \}\)

Итак, \(M_2\) \(=\) \(\{ -1000, -999, \ldots, -1, 0, 1, \ldots, 999, 1000, 1001 \}\)

Условия для функции-модификатора \(f\)

  1. Комбинирующая функция \(C\):
    Определим эту функцию непосредственно по условиям объединения и условию нейтрального маркера.

    • Условие объединения: \(\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)\).
      Упростим левую и правую части условия, учитывая определение функции-модификатора \(f \left( g, m \right) = m\).
      Левая часть: \(f \left( a, {C \left( m_{1}, m_{2} \right)} \right)\) \(=\) \(C \left( m_{1}, m_{2} \right)\)
      Правая часть: \(f \left( {f \left( a, m_{1} \right)}, m_{2} \right)\) \(=\) \(f \left( m_{1}, m_{2} \right)\) \(=\) \(m_{2}\).
      Поскольку левая часть должна равняться правой, \(C \left( m_1, m_2 \right)\) \(=\) \(m_2\).
    • Условие нейтрального маркера: полученная в результате проверки условия объединения функция \(C \left( m_1, m_2 \right)\) \(=\) \(m_2\) удовлетворяет условию нейтрального маркера: \(C \left( e_M, m_2 \right)\) \(=\) \(m_2\).

    В итоге формула для функции \(C\) следующая: \(\forall m_1 \in M_2\), \(\forall m_2 \in M\), \(C \left( m_1, m_2 \right)\) \(=\) \(m_2\)

  2. Распределяющая функция \(K\):
    Итак, пусть задан произвольный отрезок \(\left[ l, r \right]\), к которому применяется модификатор \(m \in M\), \(a_{l}\), \(a_{l+1}\), \(\ldots\), \(a_{r-1}\), \(a_{r}\) – модифицируемые элементы этого отрезка, и \(\delta = r – l + 1 \ge 1\) – количество этих элементов. Для распределяющей функции \(K\) должно быть выполнено условие:
    \(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)\)
    Поскольку \(\circ = +\), и \(\forall g \in G\), \(\forall m \in M\), \(f \left( g, m \right) = m\), в условии получим следующие преобразования:
    Левая часть: \(f \left( {a_{l} \circ a_{l+1} \circ \ldots \circ a_{r-1} \circ a_{r}}, {K \left( m, \delta \right)} \right)\) \(=\) \(K \left( m, \delta \right)\)
    Правая часть (учтём то, что в ней \(\delta\) слагаемых): \(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)\) \(=\) \(f \left( a_{l}, m \right) + f \left( a_{l+1}, m \right) + \ldots + f \left( a_{r-1}, m \right) + f \left( a_{r}, m \right)\) \(=\) \(m + m + \ldots + m + m\) \(=\) \(\delta \cdot m\).
    Итак, мы получили определение для распределяющей функции \(K\): \(K \left( m, \delta \right) = \delta \cdot m\)
  3. Расширенная функция-модификатор \(F\):
    По определению, \(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)\) \(=\) \(K \left( m, \delta \right)\) \(=\) \(\delta \cdot m\).
    Итак, \(F \left( {a_{l} + a_{l+1} + \ldots + a_{r-1} + a_{r}}, m, \delta \right) = \delta \cdot m\)

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

3. Программирование

На данном этапе всё сводится к использованию дерева отрезков по инструкции, программному описанию функций \(C\), \(F\) и операции \(\circ = +\), и связанных с условием задачи мелочей. Скажу только, что дерево отрезков в приведённой ниже программе строится методом read – дерево отрезков вызывает переданную этому методу функцию preprocessor(), поочерёдно считывая элементы данного в условии массива.

Программу можно посмотреть здесь:

Решение с включённым кодом дерева отрезков

Решение без включённого кода дерева отрезков