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

Некоторые теоретические сведения

Обобщённое условие задач на дерево отрезков, как правило, выглядит так:
«Пусть дан моноид [latex]\left(\mathbb{G}, \circ\right)[/latex], где [latex]\mathbb{G}[/latex] — некоторое непустое множество, [latex]\circ[/latex] — ассоциативная бинарная алгебраическая операция на этом множестве, имеющая нейтральный элемент, [latex]A[/latex] — последовательность (массив) элементов из [latex]\mathbb{G}[/latex], содержащая [latex]n[/latex] элементов ([latex]n \in \mathbb{N}[/latex]; с математической точки зрения [latex]A[/latex] — вектор, построенный из элементов [latex]\mathbb{G}[/latex], или [latex]А = \left( x_{0}, x_{1}, \ldots, x_{n-1} \right) \in \mathbb{G}^{n}[/latex]).
Даётся [latex]m[/latex] ([latex]m \in \mathbb{N}[/latex]) запросов двух типов:
1) вычислить значение выражения [latex]x_{i} \circ x_{i+1} \circ \ldots \circ x_{j-1} \circ x_{j}[/latex] с заданными [latex]i[/latex], [latex]j[/latex] ([latex]0 \le i \le j \le n-1[/latex], [latex]i, j \in \mathbb{N} \cup \{ 0 \}[/latex]) и вывести его;
2) заменить значение элемента с индексом [latex]k[/latex] на [latex]y[/latex] ([latex]k \in \mathbb{N} \cup \{ 0 \}[/latex], [latex]k \le n-1[/latex], [latex]y \in \mathbb{G}[/latex]).»

Как правило, человек, впервые увидевший задачу подобного рода, решает её следующим образом: для запросов первого типа (далее — запросы значения на отрезке [latex]\left[i, j\right][/latex]) создаётся вспомогательная переменная, изначально равная нейтральному элементу моноида (к примеру, если [latex]\left( \mathbb{G}, \circ \right) = \left( \mathbb{Z}, + \right)[/latex] то нейтральным элементом относительно [latex]+[/latex] является [latex]0[/latex]), и запускается цикл на заданном отрезке, который «прибавляет» к ней новые «слагаемые», а обработка запросов из пункта 2 реализуется через простое присваивание элементу массива с заданным индексом [latex]i[/latex] значения [latex]y[/latex]. Таким образом вычислительная сложность запросов замены составляет [latex]O\left(1\right)[/latex], а запросов поиска значения на отрезке [latex]\left[i, j\right][/latex] в лучшем случае составляет [latex]O\left(1\right)[/latex], когда [latex]i = j[/latex], а в худшем [latex]O\left(n\right)[/latex], когда [latex]i = 0[/latex], [latex]j = n-1[/latex].

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

Определение: массив/последовательность элементов/вектор, над которым построено дерево отрезков, называется базой дерева или просто базой, а число её элементов — её размерностью.

Задача 1: единичная модификация

Написать класс «дерево отрезков», применимый к любой задаче на моноиде, в которой присутствуют запросы замены элемента и результата операции на отрезке,
и таблицу его базовых функций и параметров.

Код класса

Описание класса

Далее [latex]n[/latex] — размерность базы дерева.

Название объекта Описание
Параметр
TYPE Тип объектов дерева, над которыми будут проводится вычисления.
Внутренние объекты
SegmentTree Массив, хранящий в себе дерево отрезков.
base_capacity Переменная, хранящая округлённую к ближайшей большей степени двойки размерность базы дерева отрезков.
g Указатель на функцию, которая представляет из себя ассоциативную бинарную операцию. Формально определяется как функция/операция.
neutral Нейтральный элемент относительно бинарной операции g.
Методы класса
construct

Аргументы:

  1. Адрес начала полуинтервала [latex]a[/latex];
  2. Адрес конца полуинтервала [latex]b[/latex];
  3. Ассоциативная бинарная операция f;
  4. Нейтральный элемент относительно f.

Генерирует базу на основе полуинтервала [latex]\left[a; b\right)[/latex], копируя его элементы внутрь дерева, и строит на основе этой базы дерево отрезков.
Вычислительная сложность: [latex]O\left(n\right)[/latex].

read_and_construct Аргументы:

  1. Размер базы дерева;
  2. Функция-препроцессор;
  3. Ассоциативная бинарная операция f;
  4. Нейтральный элемент относительно f.

Генерирует базу на основе элементов, возвращаемых функцией-препроцессором, и строит на их основе дерево отрезков.
Вычислительная сложность: [latex]O\left(n\right)[/latex].

assign Аргументы:

  1. Индекс элемента;
  2. Новое значение элемента.

Заменяет значение элемента с заданным индексом на новое.
Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].

result_on_segment Аргументы:

  1. Индекс левого конца отрезка;
  2. Индекс правого конца отрезка.

Возвращает результат функции на заданном отрезке.
Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].

Инструкция по применению

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

Построение:

  • Создать тип объектов (структуру данных), который будет использоваться в дереве для вычислений; (в зависимости от задачи. Вполне может быть, что необходимый для решения задачи класс уже создан. Например — int или double.)
  • Инициализировать дерево отрезков, передав классу segments_tree в качестве параметра тип объектов, над которыми будут проводиться вычисления, и задав дереву имя. (инициализация класса segments_tree происходит аналогично инициализации класса vector)
  • Построить дерево отрезков на основе заданных элементов при помощи метода construct или read_and_construct, передав методу соответствующие параметры (упомянутые в таблице выше);

Далее для вычисления результатов на отрезках и модификаций элементов с заданным индексом использовать методы result_on_segment и assign соответственно.

Пример использования

Примечание: условие и альтернативное решение приведённой ниже задачи находится по этой ссылке.

Решение задачи №4082 на www.e-olymp.com

Так как в задаче необходимо выводить знак или произведения на заданных отрезках (либо нуль), то очевидно, что сами числа не интересуют нас. Тогда каждое из них можно представить в виде пары (zero, plus)[latex]= \left(a, b\right) \in \mathbb{B}^{2}[/latex] (где [latex]\mathbb{B}[/latex] — булево множество), где первый элемент пар [latex]a[/latex] будет характеризовать равенство числа нулю, а [latex]b[/latex] — его положительность. Назовём структуру данных пар такого типа number_sign. Функция make_number_sign будет преобразовывать числа типа short в number_sign. Затем определим для этой структуры функцию умножения prod формулой prod(number_sign a, number_sign b)[latex]=[/latex] (a.zero|b.zero, !(a.plus^b.plus));. В первой части формулы используется дизъюнкция, так как произведение нуля и произвольного числа всегда должно возвращать нуль, а во второй части — эквиваленция, так как результат произведения является отрицательным, если оба аргумента различны по знаку.

Затем, предварительно считав размер базы, конструируем дерево отрезков методом read_and_construct, передавая ему число элементов базы, анонимную функцию-препроцессор, которая считывает элементы базы из входного потока и которая преобразует их в тип данных number_sign, функцию произведения prod и её нейтральный элемент number_sign(), являющийся парой [latex]\left(0, 1\right)[/latex], который по сути представляет из себя число [latex]+1[/latex] (нейтральный элемент умножения).

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

Фрагмент кода

Задача 2

Дополнить класс «дерево отрезков» из первой задачи таким образом, чтобы для базы дерева были реализованы:

  • параметры «вместимость» и «размер»;
  • функции добавления нового элемента в базу;
  • функции, возвращающие размер базы и вместимость дерева;
  • функция изменения размера базы.

Написать таблицу новых функций и параметров.

Код класса

Описание дополнительных объектов класса

Название объекта Описание
Новый внутренний объект
base_size Переменная, хранящая размерность базы дерева отрезков.
Новые методы класса
begin

Аргументы: отсутствуют.
Возвращает адрес начала базы.
Вычислительная сложность: константа.

end Аргументы: отсутствуют.
Возвращает адрес конца базы.
Вычислительная сложность: константа.
push_back Аргумент: значение нового элемента базы.
Добавляет новый элемент в конец базы.
Вычислительная сложность: если база заполнена, то [latex]O\left(n\right)[/latex], иначе — [latex]O\left(\log_{2}{n}\right)[/latex].

pop_back

Аргументы: отсутствуют.
Удаляет элемент в конце базы.
Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].

insert

Аргументы:

  1. Индекс нового элемента;
  2. Значение нового элемента.

Добавляет на заданную позицию базы новый элемент с заданным значением.
Вычислительная сложность: [latex]O\left(n\right)[/latex].

erase

Аргумент: индекс удаляемого элемента.
Удаляет из базы элемент с заданным индексом.
Вычислительная сложность: [latex]O\left(n\right)[/latex].

size

Аргументы: отсутствуют.
Возвращает размерность базы дерева.
Вычислительная сложность: константа.

capacity

Аргументы: отсутствуют.
Возвращает размерность базы дерева, округлённую к ближайшей большей степени двойки. Позволяет оценить число неиспользованных ячеек, на которые уже выделена память.
Вычислительная сложность: константа.

resize

Аргумент: новый размер базы.
Изменяет размер базы дерева, и преобразовывает незадействованные элементы в нейтральные
Вычислительная сложность: [latex]O\left(n\right)[/latex], если новый размер базы превысил вместимость дерева или является меньше, чем старый, и константа в противном случае.

Ссылки

А719б

Условие

Симметричные квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex] заданы последовательностями из [latex]\frac{n(n+1)}{2}[/latex] чисел аналогично правым треугольным матрицам. Получить в аналогичном виде матрицу [latex]A^{2}-B^{2}[/latex].


Решение

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

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


Замечание 1

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

Пример

[latex] \left(\begin{array}{ccc} 1 & 1 & 3 \\ 1 & 4 & 5 \\ 3 & 5 & 0\end{array} \right) \cdot \left( \begin{array}{ccc} 4 & 0 & 0 \\ 0 & 4 & 3 \\ 0 & 3 & 2 \end{array} \right) = \left( \begin{array}{ccc} 4 & 13 & 9 \\ 4 & 31 & 22 \\ 12 & 20 & 15 \end{array} \right)[/latex]


Замечание 2

Степень симметрической матрицы также является симметрической матрицей. Доказательство основано на представлении матрицы как представления линейного оператора и на свойствах эрмитовых операторов.


Во всех дальнейших выкладках подразумевается, что матрица представлена линейным массивом из [latex]\frac{n(n+1)}{2}[/latex] элементов.

Для начала, заметим, что элемент [latex]c_{i,j}[/latex] матрицы [latex]C=A^{2}[/latex], равен скалярному произведению (как векторов в стандартном базисе) [latex]i[/latex]-ой строки матрицы [latex]A[/latex] на [latex]j[/latex]-ую её строку (в силу того, что в симметричной матрице [latex]j[/latex]-ая строка совпадает с [latex]j[/latex]-м столбцом). Следовательно, для возведения в степень симметричной матрицы необходимо и достаточно реализовать операцию скалярного перемножения двух её строк.

Тогда следует понять, как по данному представлению матрицы получить её [latex]i[/latex]-ую строку. Для удобства, выпишем имеющиеся элементы в виде полной матрицы. Заметим, что первым элементом [latex]i[/latex]-ой строки будет [latex]i[/latex]-ый элемент первой строки, и обобщим это наблюдение. Обозначим позицию текущего интересующего нас элемента [latex]i[/latex]-ой строки как [latex]j[/latex]. Если [latex]j < i[/latex], то следует выбрать [latex]i[/latex]-ый элемент [latex]j[/latex]-ой строки, иначе следует выбрать все элементы [latex]j[/latex]-ой строки, лежащие правее данного. Графически можно интерпретировать алгоритм таким образом: начиная с [latex]i[/latex]-го элемента первой строки, спускаться вертикально вниз по матрице до тех пор, пока не будет достигнута [latex]i[/latex]-ая строка, далее — двигаться вправо до конца строки. Наглядность алгоритма позволяет легко воплотить его программно.
Следует только пронаблюдать, как изменяются расстояния между элементами, лежащими один под другим, при движении вниз по строкам матрицы, что позволит легко перенести алгоритм на линейное представление верхней треугольной матрицы. Предлагаем читателю самому проделать это несложное, но наглядное упражнение, для лучшего понимания алгоритма.

Теперь можно перейти непосредственно к реализации.


Тесты

[latex]n[/latex] [latex]A[/latex] [latex]B[/latex] [latex]A^{2}-B^{2}[/latex]
2 1 2 5 7 4 8 -60 -48 -51
4 1 7 3 -2 3 1 9 2 8 11 4 5 11 -3 4 -7 22 1 4 0 -108 116 -8 -79 -434 -10 75 -109 290 -239

Реализация

ideone: http://ideone.com/Dyte8l


Тесты

Детали реализации

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

  • Формулировка задачи не оговаривает тип элементов матрицы, так что класс [latex]symmetric\_matrix[/latex] является шаблоном, пригодным для типов данных, поддерживающих операции сложения, вычитания и умножения (соответствующие операторы определены внутри класса).
  • Алгоритм бинарного возведения матрицы в степень полезен при решении более широкого круга задач, в связи с чем также реализован. При необходимости, программа легко обобщается на большие степени матрицы.
  • Предусмотрены три типа конструкторов: конструктор по умолчанию и два параметрических конструктора, один из которых позволяет заполнить матрицу некоторым наперед заданным значением.
  • Для удобства работы с заданным представлением данных, добавлен синтаксический сахар: перегружен оператор [latex][][/latex], осуществляющий доступ к заданному элементу матрицы в линейном её представлении.