Как выглядит корень дерева

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

Обновление на отрезке

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

Поиск подотрезка с наибольшей суммой

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

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

Как смотрится корень дерева

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

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

Как же выстроить дерево отрезков с таковыми данными?

Как смотрится корень дерева

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

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

Значит, ответ в текущей вершине равен максимуму из этих трёх величин.

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

struct data int sum, pref, suff, ans;; data combine (data l, data r) data res; = + ; = max (, + ); = max (, + ); = max (max (, ), + );return res;

Таким образом, мы научились строить дерево отрезков.

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

Как смотрится корень дерева

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

data make_data (int val) data res; = val; = = = max (0, val);return res; void build (int a[], int v, int tl, int tr)if(tl == tr) t[v]= make_data (a[tl]);elseinttm=(tl + tr)/2; build (a, v*2, tl, tm); build (a, v*2+1, tm+1, tr); t[v]= combine (t[v*2], t[v*2+1]); void update (int v, int tl, int tr, int pos, int new_val)if(tl == tr) t[v]= make_data (new_val);elseinttm=(tl + tr)/2;if(pos <=tm) update (v*2, tl, tm, pos, new_val);else update (v*2+1, tm+1, tr, pos, new_val); t[v]= combine (t[v*2], t[v*2+1]);

Осталось разобраться с ответом на запрос.

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

data query (int v, int tl, int tr, int l, int r)if(l == tl && tr == r)return t[v];inttm=(tl + tr)/2;if(r <=tm)return query (v*2, tl, tm, l, r);if(l >tm)return query (v*2+1, tm+1, tr, l, r);return combine ( query (v*2, tl, tm, l, tm), query (v*2+1, tm+1, tr, tm+1, r));

Сохранение всего подмассива в каждой вершине дерева отрезков

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

Таковым образом, корень дерева отрезков будет хранить все элементы массива, левый отпрыск корня — первую половину массива, правый отпрыск корня — вторую половину, и так далее.

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

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

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

Почему это так? Поэтому что каждое число попадает в отрезков дерева отрезков (хотя бы поэтому, что высота дерева отрезков есть ).

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

Ниже описано несколько обычных применений таковой структуры данных. Стоит сходу отметить явную аналогию деревьев отрезков этого типа с двумерными структурами данных (собственно, в каком-то смысле это и есть двумерная структура данных, но с достаточно ограниченными возможностями).

Поиск меньшего числа, больше или равного данного, в указанном отрезке.

Ускорение с помощью техники «частичного каскадирования»

Улучшим время ответа на запрос поиска до времени с помощью внедрения техники «частичного каскадирования» («fractional cascading»).

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

Как смотрится корень дерева

В самом деле, ответ на запрос поиска заключается в том, что мы разбиваем нашу задачку на несколько подзадач, любая из которых потом решается бинарным поиском по числу . Частичное каскадирование дозволяет заменить все эти двоичные поиски на один.

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

Если бы мы решали задачку «в лоб», то обязаны были бы запустить бинарный поиск по каждому из этих списков, что, ежели этих списков много, становится очень значимым фактором: ежели всего списков , то асимптотика получится , где — суммарный размер всех списков (асимптотика такая, поэтому что худший вариант — когда все списки приблизительно равны друг другу по длине, т.е.

равны ).

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

Техника частичного каскадирования идёт далее в решении данной нам задачки и достигает употребления памяти при том же самом времени ответа на запрос .

(Для этого мы храним не один большой перечень длины , а опять возвращаемся к перечням, но совместно с каждым перечнем храним каждый 2-ой элемент из последующего списка; нам опять придётся совместно с каждым числом записывать его позицию в обоих перечнях (текущем и следующем), но это дозволит по-прежнему отлично отвечать на запрос: мы делаем двоичный поиск по первому списку, а потом идём по сиим перечням по порядку, переходя каждый раз в последующий перечень с помощью предпосчитанных указателей, и делая один шаг на лево, беря во внимание тем самым, что половина чисел последующего перечня учтена не была).

Но нам в нашем приложении к дереву отрезков не нужна полная мощь данной для нас техники.

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

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

Проще всего эту технику использовать к задачке, когда запросы модификации отсутствуют, — тогда эти позиции представляют собой просто числа, а подсчитывать их при построении дерева чрезвычайно просто снутри метода слияния 2-ух отсортированных последовательностей.

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

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

Прибавление на отрезке

Начнём рассмотрение деревьев отрезков такового рода с самого обычного случая: запрос модификации представляет собой прибавление ко всем числам на неком подотрезке некого числа .

Запрос чтения — по-прежнему считывание значения некого числа .

Чтобы делать запрос добавления отлично, будем хранить в каждой вершине дерева отрезков, сколько нужно прибавить ко всем числам этого отрезка полностью. К примеру, ежели приходит запрос «прибавить ко всему массиву число 2», то мы поставим в корне дерева число . Тем самым мы сможем обрабатывать запрос добавления на хоть каком подотрезке отлично, заместо того чтоб изменять все значений.

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

void build (int a[], int v, int tl, int tr)if(tl == tr) t[v]= a[tl];elseinttm=(tl + tr)/2; build (a, v*2, tl, tm); build (a, v*2+1, tm+1, tr); void update (int v, int tl, int tr, int l, int r, int add)if(l > r)return;if(l == tl && tr == r) t[v]+= add;elseinttm=(tl + tr)/2; update (v*2, tl, tm, l, min(r,tm), add); update (v*2+1, tm+1, tr, max(l,tm+1), r, add); int get (int v, int tl, int tr, int pos)if(tl == tr)return t[v];inttm=(tl + tr)/2;if(pos <=tm)return t[v]+ get (v*2, tl, tm, pos);elsereturn t[v]+ get (v*2+1, tm+1, tr, pos);

Присвоение на отрезке

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

В качестве второго запроса будем разглядывать считывание значения массива .

Чтобы делать модификацию на целом отрезке, придётся в каждой вершине дерева отрезков хранить, покрашен ли этот отрезок полностью в какое-либо число либо нет (и ежели покрашен, то хранить само это число). Это дозволит нам делать «запаздывающее» обновление дерева отрезков: при запросе модификации мы, заместо того чтоб поменять значения во множестве вершин дерева отрезков, поменяем лишь некие из них, оставив флаги «покрашен» для остальных отрезков, что значит, что весь этот отрезок совместно со своими подотрезками должен быть покрашен в этот цвет.

Итак, опосля выполнения запроса модификации дерево отрезков становится, вообщем говоря, неактуальным — в нём остались недовыполненными некие модификации.

Например, ежели пришёл запрос модификации «присвоить всему массиву какое-то число», то в дереве отрезков мы создадим единственное изменение — пометим корень дерева, что он покрашен полностью в это число.

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

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

Выход таков: произвести проталкивание инфы из корня, т.е.

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

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

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

Вызывать эту функцию следует в самом начале функций обработки запросов (но не вызывать её из листьев, ведь из листа проталкивать информацию не нужно, да и некуда).

void push (int v)if(t[v]!=-1) t[v*2]= t[v*2+1]= t[v]; t[v]=-1; void update (int v, int tl, int tr, int l, int r, int color)if(l > r)return;if(l == tl && tr == r) t[v]= color;else push (v);inttm=(tl + tr)/2; update (v*2, tl, tm, l, min(r,tm), color); update (v*2+1, tm+1, tr, max(l,tm+1), r, color); int get (int v, int tl, int tr, int pos)if(tl == tr)return t[v]; push (v);inttm=(tl + tr)/2;if(pos <=tm)return get (v*2, tl, tm, pos);elsereturn get (v*2+1, tm+1, tr, pos);

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

Подсчёт количества нулей, поиск -го нуля

В данной нам задачке мы желаем научиться отвечать на запрос количества нулей в данном отрезке массива, а также на запрос нахождения -го нулевого элемента.

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

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

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

Как смотрится корень дерева

В самом деле, чтоб осознать, в какого отпрыска нам нужно перебегать, довольно поглядеть на значение, записанное в левом сыне: ежели оно больше или равно , то перебегать нужно в левого отпрыска (потому что в его отрезке есть как минимум нулей), а по другому — перебегать в правого сына.

При реализации можно отсечь вариант, когда -го нуля не существует, ещё при входе в функцию, возвратив в качестве ответа, к примеру, .

int find_kth (int v, int tl, int tr, int k)if(k > t[v])return-1;if(tl == tr)return tl;inttm=(tl + tr)/2;if(t[v*2]>= k)return find_kth (v*2, tl, tm, k);elsereturn find_kth (v*2+1, tm+1, tr, k — t[v*2]);

Поиск префикса массива с данной суммой

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

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

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

Тогда ответ на запрос поиска будет представлять собой один таковой спуск по дереву, а, следовательно, будет выполняться за .

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

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

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

Беря во внимание, что вообщем говоря число во входном массиве могут повторяться, хорошим выбором является структура данных STL .

Построение такового дерева отрезков происходит приблизительно так же, как и в предшествующей задачке, лишь сейчас нужно объединять не отсортированные списки, а , что приведёт к тому, что асимптотика построения ухудшится до (хотя, по-видимому, красно-чёрные деревья разрешают выполнить слияние 2-ух деревьев за линейное время, но библиотека STL этого не гарантирует).

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

Наконец, запрос модификации.

Для его обработки мы должны спуститься по дереву, внеся конфигурации во все списков, содержащих затрагиваемый элемент.

Как смотрится корень дерева

Мы просто удаляем старенькое значение этого элемента (не забыв, что нам не нужно удалить совместно с ним все повторы этого числа) и вставляем его новое значение.

void update (int v, int tl, int tr, int pos, int new_val) t[v].erase(t[v].find(a[pos])); t[v].insert(new_val);if(tl != tr)inttm=(tl + tr)/2;if(pos <=tm) update (v*2, tl, tm, pos, new_val);else update (v*2+1, tm+1, tr, pos, new_val);else a[pos]= new_val;

Обработка этого запроса происходит также за время .

Другие направления

Здесь были рассмотрены лишь базисные внедрения деревьев отрезков в задачках с модификациями на отрезке.

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

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

Более сложные функции и запросы

Улучшения дерева отрезков в этом направлении могут быть как достаточно очевидными (как в случае минимума/максимума заместо суммы), так и очень и очень нетривиальными.

Поиск меньшего числа, больше или равного данного, в указанном отрезке.

Запросов модификации нет

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

Построим дерево отрезков, в котором в каждой вершине будем хранить отсортированный перечень всех чисел, встречающихся на соответственном отрезке. К примеру, корень будет содержать массив в отсортированном виде. Как выстроить такое дерево отрезков очень эффективно? Для этого подойдём к задачке, как традиционно, с точки зрения рекурсии: пусть для левого и правого отпрыской текущей вершины эти списки уже построены, и нам требуется выстроить этот перечень для текущей вершины. При таковой постановке вопросика становится практически разумеется, что это можно сделать за линейное время: нам просто нужно объединить два отсортированных перечня в один, что делается одним проходом по ним с 2-мя указателями.

Юзерам C++ ещё проще, поэтому что этот метод слияния уже включён в обычную библиотеку STL:

vector<int> t[4*MAXN]; void build (int a[], int v, int tl, int tr)if(tl == tr) t[v]= vector<int>(1, a[tl]);elseinttm=(tl + tr)/2; build (a, v*2, tl, tm); build (a, v*2+1, tm+1, tr); merge (t[v*2].begin(), t[v*2].end(), t[v*2+1].begin(), t[v*2+1].end(), back_inserter (t[v]));

Мы уже знаем, что построенное таковым образом дерево отрезков будет занимать памяти.

Как смотрится корень дерева

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

Теперь разглядим ответ на запрос. Будем спускаться по дереву, как это делает обычный ответ на запрос в дереве отрезков, разбивая наш отрезок на несколько подотрезков (порядка штук).

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

Итак, мы пришли в какую-то вершину дерева отрезков и желаем посчитать ответ на ней, т.е. отыскать малое число, больше или равное данного . Для этого нам всего только нужно выполнить бинарный поиск по списку, посчитанному в данной нам вершине дерева, и вернуть 1-ое число из этого перечня, больше или равное .

Таким образом, ответ на запрос в одном подотрезке происходит за , а весь запрос обрабатывается за время .

int query (int v, int tl, int tr, int l, int r, int x)if(l > r)return INF;if(l == tl && tr == r) vector<int>::iterator pos = lower_bound (t[v].begin(), t[v].end(), x);if(pos != t[v].end())return*pos;return INF;inttm=(tl + tr)/2;return min ( query (v*2, tl, tm, l, min(r,tm), x), query (v*2+1, tm+1, tr, max(l,tm+1), r, x));

Константа равна некому большому числу, заранее большему, чем хоть какое число в массиве.

Она несёт смысл «ответа в данном отрезке не существует».

Поиск минимума/максимума

Немного изменим условие задачки, описанной выше: заместо запроса суммы будем создавать сейчас запрос минимума/максимума на отрезке.

Тогда дерево отрезков для таковой задачки фактически ничем не различается от дерева отрезков, описанного выше. Просто нужно поменять метод вычисления в функциях и , а также вычисление возвращаемого ответа в функции (заменить суммирование на минимум/максимум).

Другие вероятные направления

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

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

Обобщение на огромные размерности

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

Как смотрится корень дерева

Ежели в одномерном случае мы разбивали индексы массива на отрезки, то в двумерном случае сейчас будем поначалу разбивать всё по первым индексам, а для каждого отрезка по первым индексам — строить обыденное дерево отрезков по вторым индексам. Таковым образом, основная мысль решения — это вкладывание деревьев отрезков по вторым индексам вовнутрь дерева отрезков по первым индексам.

Поясним эту идею на примере определенной задачи.

Поиск минимума/максимума и количества раз, которое он встречается

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

Для решения данной для нас задачки в каждой вершине дерева отрезков будем хранить пару чисел: не считая максимума количество его вхождений на соответственном отрезке.

Тогда при построении дерева мы должны просто по двум таковым парам, приобретенным от отпрыской текущей вершины, получать пару для текущей вершины.

Объединение 2-ух таковых пар в одну стоит выделить в отдельную функцию, так как эту операцию нужно будет создавать и в запросе модификации, и в запросе поиска максимума.

pair<int,int> t[4*MAXN]; pair<int,int> combine (pair<int,int> a, pair<int,int> b)if(> )return a;if(> )return b;return make_pair (, + ); void build (int a[], int v, int tl, int tr)if(tl == tr) t[v]= make_pair (a[tl], 1);elseinttm=(tl + tr)/2; build (a, v*2, tl, tm); build (a, v*2+1, tm+1, tr); t[v]= combine (t[v*2], t[v*2+1]); pair<int,int> get_max (int v, int tl, int tr, int l, int r)if(l > r)return make_pair (-INF, 0);if(l == tl && r == tr)return t[v];inttm=(tl + tr)/2;return combine ( get_max (v*2, tl, tm, l, min(r,tm)), get_max (v*2+1, tm+1, tr, max(l,tm+1), r)); void update (int v, int tl, int tr, int pos, int new_val)if(tl == tr) t[v]= make_pair (new_val, 1);elseinttm=(tl + tr)/2;if(pos <=tm) update (v*2, tl, tm, pos, new_val);else update (v*2+1, tm+1, tr, pos, new_val); t[v]= combine (t[v*2], t[v*2+1]);

Поиск большего общего делителя / меньшего общего кратного

Т.е.

мы желаем научиться находить НОД/НОК всех чисел в данном отрезке массива.

Это достаточно увлекательное обобщение дерева отрезков выходит полностью таковым же путём, как и деревья отрезков для суммы/минимума/максимума: довольно просто хранить в каждой вершине дерева НОД/НОК всех чисел в соответственном отрезке массива.

Прибавление на отрезке, запрос максимума

Пусть сейчас запросом модификации опять будет запрос добавления ко всем числам некого подотрезка 1-го и того же числа, а запросом чтения будет нахождение максимума в неком подотрезке.

Тогда в каждой вершине дерева отрезков нужно будет дополнительно хранить максимум на всём этом подотрезке.

Но тонкость тут заключается в том, как нужно пересчитывать эти значения.

Например, пусть произошёл запрос «прибавить ко всей первой половине, т.е. , число 2». Тогда в дереве это отразится записью числа в левого отпрыска корня. Как сейчас посчитать новое значение максимума в левом отпрыску и в корне? Тут становится принципиально не запутаться — какой максимум хранится в вершине дерева: максимум без учёта добавления на всей данной вершине, либо же с учётом его. Выбрать можно хоть какой из этих подходов, но основное — поочередно употреблять его везде.

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

Двумерное дерево отрезков в простом варианте

Дана прямоугольная матрица , и поступают запросы поиска суммы (или минимума/максимума) на неких подпрямоугольниках , а также запросы модификации отдельных частей матрицы (т.е.

запросы вида ).

Итак, будем строить двумерное дерево отрезков: поначалу дерево отрезков по первой координате (), потом — по 2-ой ().

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

в этот момент мы вспоминаем, что у нас есть ещё и 2-ая координата; но т.к. в этот момент уже зафиксировано, что 1-ая координата есть некий отрезок , то мы практически работаем с таковой полосой , и для неё строим дерево отрезков.

Приведём реализацию операции построения двумерного дерева. Она практически представляет собой два отдельных блока: построение дерева отрезков по координате () и по координате (). Ежели 1-ая функция практически ничем не различается от обыденного одномерного дерева, то 2-ая обязана разбираться раздельно с 2-мя случаями: когда текущий отрезок по первой координате () имеет единичную длину, и когда — длину, огромную единицы. В первом случае мы просто берём необходимое значение из матрицы , а во втором — объединяем значения 2-ух деревьев отрезков из левого отпрыска и правого отпрыска по координате .

void build_y (int vx, int lx, int rx, int vy, int ly, int ry)if(ly == ry)if(lx == rx) t[vx][vy]= a[lx][ly];else t[vx][vy]= t[vx*2][vy]+ t[vx*2+1]

Дерево отрезков

Дерево отрезков — это структура данных, которая дозволяет отлично (т.е.

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

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

Кроме приведённых выше видов операций с деревьями отрезков, также возможны и еще наиболее сложные операции (см. раздел «Усложнённые версии дерева отрезков»). В частности, дерево отрезков просто обобщается на огромные размерности: к примеру, для решения задачки о поиске суммы/минимума в неком подпрямоугольнике данной матрицы (правда, уже лишь за время ).

Важной индивидуальностью деревьев отрезков является то, что они потребляют линейный объём памяти: обычному дереву отрезков требуется порядка частей памяти для работы над массивом размера .

Описание дерева отрезков в базисном варианте

Для начала разглядим простой вариант дерева отрезков — дерево отрезков для сумм.

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

Запрос суммы

Рассмотрим сейчас запрос суммы. На вход поступают два числа и , и мы должны за время посчитать сумму чисел на отрезке .

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

Вначале мы встаём в корень дерева отрезков. Поглядим, в какие из 2-ух его отпрыской попадает отрезок запроса (напомним, что сыновья корня дерева отрезков — это отрезки и ). Возможны два варианта: что отрезок попадает лишь в 1-го отпрыска корня, и что, напротив, отрезок пересекается с обоими сыновьями.

Первый вариант прост: просто перейдём в того отпрыска, в котором лежит наш отрезок-запрос, и применим описываемый тут метод к текущей вершине.

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

Как смотрится корень дерева

Другими словами, ежели левый отпрыск представлял отрезок , а правый — отрезок (заметим, что ), то мы перейдём в левого отпрыска с запросом , а в правого — с запросом .

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

Но рекурсивные вызовы будем делать не всегда: ежели текущий запрос совпал с границами отрезка в текущей вершине дерева отрезков, то в качестве ответа будем возвращать предвычисленное значение суммы на этом отрезке, записанное в дереве отрезков.

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

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

Утверждается, что таковых отрезков не могло быть наиболее четырёх; тогда, беря во внимание оценку для высоты дерева, мы и получаем подходящую асимптотику времени работы алгоритма.

Покажем, что эта оценка о четырёх отрезках верна. В самом деле, на нулевом уровне дерева запросом затрагивается единственная вершина — корень дерева. Далее на первом уровне рекурсивный вызов в худшем случае разбивается на два рекурсивных вызова, но принципиально тут то, что запросы в этих 2-ух вызовах будут соседствовать, т.е.

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

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

Ежели делать это разбиение правильным образом, то благодаря структуре дерева отрезков число нужных подотрезков постоянно будет , что и даёт эффективность работы дерева отрезков.

Запрос обновления

Напомним, что запрос обновления получает на вход индекс и значение , и перестраивает дерево отрезков таковым образом, чтоб оно соответствовало новенькому значению . Этот запрос должен также выполняться за время .

Это наиболее обычной запрос по сопоставлению с запросом подсчёта суммы. Дело в том, что элемент участвует лишь в относительно маленьком числе вершин дерева отрезков: а конкретно, в верхушках — по одной с каждого уровня.

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

как сумма значений по обоим сыновьям текущей вершины).

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

Итак, что же представляет из себя дерево отрезков?

Подсчитаем и запомним где-нибудь сумму частей всего массива, т.е. отрезка . Также посчитаем сумму на 2-ух половинках этого массива: и . Каждую из этих 2-ух половинок в свою очередь разобьём пополам, посчитаем и сохраним сумму на них, позже опять разобьём пополам, и так дальше, пока текущий отрезок не достигнет длины . Другими словами, мы стартуем с отрезка и каждый раз делим текущий отрезок надвое (если он ещё не стал отрезком единичной длины), вызывая потом эту же функцию от обеих половинок; для каждого такового отрезка мы храним сумму чисел на нём.

Можно говорить, что эти отрезки, на которых мы считали сумму, образуют дерево: корень этого дерева — отрезок , а любая вершина имеет ровно 2-ух отпрыской (кроме вершин-листьев, у которых отрезок имеет длину ).

Отсюда и происходит заглавие — «дерево отрезков» (хотя при реализации традиционно никакого дерева очевидно не строится, но о этом ниже в разделе реализации).

Итак, мы обрисовали структуру дерева отрезков. Сходу заметим, что оно имеет линейный размер, а конкретно, содержит наименее вершин. Осознать это можно последующим образом: 1-ый уровень дерева отрезков содержит одну вершину (отрезок ), 2-ой уровень — в худшем случае две вершины, на 3-ем уровне в худшем случае будет четыре вершины, и так дальше, пока число вершин не достигнет . Таковым образом, число вершин в худшем случае оценивается суммой .

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

К примеру, при левый отпрыск корня есть отрезок , имеющий 2-ух потомков, в то время как правый отпрыск корня — отрезок , являющийся листом. Никаких особенных сложностей при реализации это не составляет, но тем не наименее это нужно иметь в виду.

Высота дерева отрезков есть величина — к примеру, поэтому что длина отрезка в корне дерева равна , а при переходе на один уровень вниз длина отрезков миниатюризируется приблизительно вдвое.

Построение

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

Комфортно обрисовывать эту операцию рекурсивно: мы запускаем функцию построения от корня дерева отрезков, а сама процедура построения, ежели её вызвали не от листа, вызывает себя от каждого из 2-ух отпрыской и суммирует вычисленные значения, а ежели её вызвали от листа — то просто записывает в себя значение этого элемента массива.

Асимптотика построения дерева отрезков составит, таковым образом, .

Реализация

Основной реализационный момент — это то, как хранить дерево отрезков в памяти.

Как смотрится корень дерева

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

Такой приём существенно упрощает программирование дерева отрезков, — сейчас нам не необходимо хранить в памяти структуру дерева отрезков, а лишь только завести какой-нибудь массив для сумм на каждом отрезке дерева отрезков.

Стоит лишь отметить, что размер этого массива при таковой нумерации нужно ставить не , а .

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

Итак, дерево отрезков мы храним просто в виде массива , размера в четыре раза больше размера входных данных:

int n, t[4*MAXN];

Процедура построения дерева отрезков по данному массиву смотрится последующим образом: это рекурсивная функция, ей передаётся сам массив , номер текущей вершины дерева, и границы и отрезка, соответственного текущей вершине дерева.

Из основной программы вызывать эту функцию следует с параметрами , , .

void build (int a[], int v, int tl, int tr)if(tl == tr) t[v]= a[tl];elseinttm=(tl + tr)/2; build (a, v*2, tl, tm); build (a, v*2+1, tm+1, tr); t[v]= t[v*2]+ t[v*2+1];

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

int sum (int v, int tl, int tr, int l, int r)if(l > r)return0;if(l == tl && r == tr)return t[v];inttm=(tl + tr)/2;return sum (v*2, tl, tm, l, min(r,tm))+ sum (v*2+1, tm+1, tr, max(l,tm+1), r);

Наконец, запрос модификации.

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

void update (int v, int tl, int tr, int pos, int new_val)if(tl == tr) t[v]= new_val;elseinttm=(tl + tr)/2;if(pos <=tm) update (v*2, tl, tm, pos, new_val);else update (v*2+1, tm+1, tr, pos, new_val); t[v]= t[v*2]+ t[v*2+1];

Стоит отметить, что функцию просто сделать нерекурсивной, так как рекурсия в ней хвостовая, т.е.

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

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

ВИДЕО ПО ТЕМЕ: