40
правок
Изменения
Нет описания правки
===Поддержание корректности ключей <tex>X</tex>===
Единственное действие, обеспечивающее корректность этих ключей заключается в том, что после любого действия с детьми вершины нужно записать в ее ключ <tex>X</tex> сумму этих ключей в ее новых детях, увеличенную на единицу.
==Применение описанного дерева==
Что же мы получили? У нас есть структура, от которой можно без проблем отрезать слева кусок произвольной длины и слить два любых куска в один в нужном порядке. Теперь мы можем безбоязненно:
* вставить элемент в любое место (отрежем нужное количество слева, сольем левое дерево с деревом из одного добавленного элемента и результат {{---}} с правым деревом)
* переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке)
* совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка.
* сделав на одном исходном массиве два дерева из элементов разной четности, можно поизвращаться со сменой мест четных и нечетных на отрезке (одно из домашних заданий)
* повелевать миром
