E115. Дерево отрезков
Источник: e-maxx.ru/algo, страница PDF 368.
Дерево отрезков — это структура данных, которая позволяет эффективно (т.е. за асимптотику
)
реализовать операции следующего вида: нахождение суммы/минимума элементов массива в заданном
отрезке (
, где
и
поступают на вход алгоритма), при этом дополнительно возможно изменение элементов массива: как изменение значения одного элемента, так и изменение элементов на целом подотрезке массива
(т.е. разрешается присвоить всем элементам
какое-либо значение, либо прибавить ко всем элементам
массива какое-либо число). Вообще, дерево отрезков — очень гибкая структура, и число задач, решаемых ей, теоретически неограниченно. Помимо приведённых выше видов операций с деревьями отрезков, также возможны и гораздо более сложные операции (см. раздел "Усложнённые версии дерева отрезков"). В частности, дерево отрезков легко обобщается на большие размерности: например, для решения задачи о поиске суммы/минимума в некотором
подпрямоугольнике данной матрицы (правда, уже только за время
). Важной особенностью деревьев отрезков является то, что они потребляют линейный объём памяти: стандартному
дереву отрезков требуется порядка
элементов памяти для работы над массивом размера
.
Описание дерева отрезков в базовом варианте
Для начала рассмотрим простейший случай дерева отрезков — дерево отрезков для сумм. Если ставить
задачу формально, то у нас есть массив
, и наше дерево отрезков должно уметь находить сумму
элементов с
-го по
-ый (это запрос суммы), а также обрабатывать изменение значения одного указанного
элемента массива, т.е. фактически реагировать на присвоение
(это запрос модификации). Ещё раз
повторимся, дерево отрезков должно обрабатывать оба этих запроса за время .
Структура дерева отрезков
Итак, что же представляет из себя дерево отрезков?
Подсчитаем и запомним где-нибудь сумму элементов всего массива, т.е. отрезка
. Также
посчитаем сумму на двух половинках этого массива:
и
. Каждую из этих
двух половинок в свою очередь разобьём пополам, посчитаем и сохраним сумму на них, потом снова разобьём пополам,
и так далее, пока текущий отрезок не достигнет длины
. Иными словами, мы стартуем с отрезка
и
каждый раз делим текущий отрезок надвое (если он ещё не стал отрезком единичной длины), вызывая затем эту же процедуру от обеих половинок; для каждого такого отрезка мы храним сумму чисел на нём. Можно говорить, что эти отрезки, на которых мы считали сумму, образуют дерево: корень этого дерева —
отрезок
, а каждая вершина имеет ровно двух сыновей (кроме вершин-листьев, у которых отрезок
имеет длину
). Отсюда и происходит название — "дерево отрезков" (хотя при реализации обычно никакого дерева явно не строится, но об этом ниже в разделе реализации). Итак, мы описали структуру дерева отрезков. Сразу заметим, что оно имеет линейный размер, а
именно, содержит менее
вершин. Понять это можно следующим образом: первый уровень дерева отрезков
содержит одну вершину (отрезок
), второй уровень — в худшем случае две вершины, на третьем уровне в худшем случае будет четыре вершины, и так далее, пока число вершин не достигнет
. Таким образом, число вершин
в худшем случае оценивается суммой
.
Стоит отметить, что при
, отличных от степеней двойки, не все уровни дерева отрезков будут полностью
заполнены. Например, при
левый сын корня есть отрезок
, имеющий двух потомков, в то время
как правый сын корня — отрезок
, являющийся листом. Никаких особых сложностей при реализации это не составляет, но тем не менее это надо иметь в виду.
Высота дерева отрезков есть величина
— например, потому что длина отрезка в корне дерева равна
,
а при переходе на один уровень вниз длина отрезков уменьшается примерно вдвое.
Построение
Процесс построения дерева отрезков по заданному массиву
можно делать эффективно следующим образом,
снизу вверх: сначала запишем значения элементов
в соответствующие листья дерева, затем на основе
них посчитаем значения для вершин предыдущего уровня как сумму значений в двух листьях, затем аналогичным образом посчитаем значения для ещё одного уровня, и т.д. Удобно описывать эту операцию рекурсивно: мы запускаем процедуру построения от корня дерева отрезков, а сама процедура построения, если её вызвали не от листа, вызывает себя от каждого из двух сыновей и суммирует вычисленные значения, а если её вызвали от листа — то просто записывает в себя значение этого элемента массива.
Асимптотика построения дерева отрезков составит, таким образом,
.
Запрос суммы
Рассмотрим теперь запрос суммы. На вход поступают два числа
и
, и мы должны за время
посчитать
сумму чисел на отрезке
. Для этого мы будем спускаться по построенному дереву отрезков, используя для подсчёта ответа посчитанные ранее суммы на каждой вершине дерева. Изначально мы встаём в корень дерева отрезков. Посмотрим, в какие из двух
его сыновей попадает отрезок запроса
(напомним, что сыновья корня дерева отрезков — это
отрезки
и
). Возможны два варианта: что отрезок
попадает только в
одного сына корня, и что, наоборот, отрезок пересекается с обоими сыновьями. Первый случай прост: просто перейдём в того сына, в котором лежит наш отрезок-запрос, и применим описываемый здесь алгоритм к текущей вершине. Во втором же случае нам не остаётся других вариантов, кроме как перейти сначала в левого сына и посчитать ответ на запрос в нём, а затем — перейти в правого сына, посчитать в нём ответ и прибавить к нашему ответу. Иными
словами, если левый сын представлял отрезок
, а правый — отрезок
(заметим,
что
), то мы перейдём в левого сына с запросом
, а в правого — с запросом
. Итак, обработка запроса суммы представляет собой рекурсивную функцию, которая всякий раз вызывает себя либо от левого сына, либо от правого (не изменяя границы запроса в обоих случаях), либо от обоих сразу (при этом деля наш запрос на два соответствующих подзапроса). Однако рекурсивные вызовы будем делать не всегда: если текущий запрос совпал с границами отрезка в текущей вершине дерева отрезков, то в качестве ответа будем возвращать предвычисленное значение суммы на этом отрезке, записанное в дереве отрезков. Иными словами, вычисление запроса представляет собой спуск по дереву отрезков, который распространяется по всем нужным ветвям дерева, и для быстрой работы использующий уже посчитанные суммы по каждому отрезку в дереве отрезков.
Почему же асимптотика этого алгоритма будет
? Для этого посмотрим на каждом уровне
дерева отрезков, сколько максимум отрезков могла посетить наша рекурсивная функция при обработке какого- либо запроса. Утверждается, что таких отрезков не могло быть более четырёх; тогда, учитывая оценку
для высоты дерева, мы и получаем нужную асимптотику времени работы алгоритма. Покажем, что эта оценка о четырёх отрезках верна. В самом деле, на нулевом уровне дерева запросом затрагивается единственная вершина — корень дерева. Дальше на первом уровне рекурсивный вызов в худшем случае разбивается на два рекурсивных вызова, но важно здесь то, что запросы в этих двух вызовах будут
соседствовать, т.е. число
запроса во втором рекурсивном вызове будет на единицу больше числа
запроса в
первом рекурсивном вызове. Отсюда следует, что на следующем уровне каждый из этих двух вызовов мог породить ещё по два рекурсивных вызова, но в таком случае половина этих запросов отработает нерекурсивно, взяв нужное значение из вершины дерева отрезков. Таким образом, всякий раз у нас будет не более двух реально работающих ветвей рекурсии (можно сказать, что одна ветвь приближается к левой границе запроса, а вторая ветвь — к правой), а всего число затронутых отрезков не могло превысить высоты дерева отрезков, умноженной на четыре, т.е.
оно есть число
. В завершение можно привести и такое понимание работы запроса суммы: входной отрезок
разбивается
на несколько подотрезков, ответ на каждом из которых уже подсчитан и сохранён в дереве. Если делать это разбиение правильным образом, то благодаря структуре дерева отрезков число необходимых подотрезков всегда
будет
, что и даёт эффективность работы дерева отрезков.
Запрос обновления
Напомним, что запрос обновления получает на вход индекс
и значение
, и перестраивает дерево отрезков
таким образом, чтобы оно соответствовало новому значению
. Этот запрос должен также выполняться за
время
. Это более простой запрос по сравнению с запросом подсчёта суммы. Дело в том, что элемент
участвует только
в относительно небольшом числе вершин дерева отрезков: а именно, в
вершинах — по одной с
каждого уровня. Тогда понятно, что запрос обновления можно реализовать как рекурсивную функцию: ей передаётся текущая вершина дерева отрезков, и эта функция выполняет рекурсивный вызов от одного из двух своих сыновей (от того,
который содержит позицию
в своём отрезке), а после этого — пересчитывает значение суммы в текущей вершине точно таким же образом, как мы это делали при построении дерева отрезков (т.е. как сумма значений по обоим сыновьям текущей вершины).
Реализация
Основной реализационный момент — это то, как хранить дерево отрезков в памяти. В целях простоты мы не будем хранить дерево в явном виде, а воспользуемся таким трюком: скажем, что корень дерева имеет номер
,
его сыновья — номера
и
, их сыновья — номера с
по
, и так далее. Легко понять корректность следующей
формулы: если вершина имеет номер
, то пусть её левый сын — это вершина с номером
, а правый — с
номером
. Такой приём значительно упрощает программирование дерева отрезков, — теперь нам не нужно хранить в памяти структуру дерева отрезков, а только лишь завести какой-либо массив для сумм на каждом отрезке дерева отрезков. Стоит только отметить, что размер этого массива при такой нумерации надо ставить не
, а
. Дело в том, что
такая нумерация не идеально работает в случае, когда
не является степенью двойки — тогда появляются
пропущенные номера, которым не соответствуют никакие вершины дерева (фактически, нумерация ведёт себя
подобно тому, как если бы
округлили бы вверх до ближайшей степени двойки). Это не создаёт никаких сложностей при реализации, однако приводит к тому, что размер массива надо увеличивать до .
Итак, дерево отрезков мы храним просто в виде массива
, размера вчетверо больше размера
входных данных:
int n, t[4*MAXN];Процедура построения дерева отрезков по заданному массиву
выглядит следующим образом:
это рекурсивная функция, ей передаётся сам массив
, номер
текущей вершины дерева, и границы
и
отрезка, соответствующего текущей вершине дерева. Из основной программы вызывать эту функцию следует
с параметрами
,
,
.
void build (int a[], int v, int tl, int tr) {
if (tl == tr)t[v] = a[tl];
else {
int tm = (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)return 0;if (l == tl && r == tr)return t[v];int tm = (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;
else {
int tm = (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];
} }
Стоит отметить, что функцию
легко сделать нерекурсивной, поскольку рекурсия в ней хвостовая, т. е. разветвлений никогда не происходит: один вызов может породить только один рекурсивный вызов. При нерекурсивной реализации скорость работы может вырасти в несколько раз. Из других оптимизаций стоит упомянуть, что умножения и деления на два стоит заменить битовыми операциями — это также немного улучшает производительность дерева отрезков.
Усложнённые версии дерева отрезков
Дерево отрезков — очень гибкая структура, и позволяет делать обобщения во многих различных направлениях. Попытаемся ниже классифицировать их.
Более сложные функции и запросы
Улучшения дерева отрезков в этом направлении могут быть как довольно очевидными (как в случае минимума/ максимума вместо суммы), так и весьма и весьма нетривиальными.
Поиск минимума/максимума
Немного изменим условие задачи, описанной выше: вместо запроса суммы будем производить теперь запрос минимума/максимума на отрезке. Тогда дерево отрезков для такой задачи практически ничем не отличается от дерева отрезков, описанного выше.
Просто надо изменить способ вычисления
в функциях
и
, а также вычисление
возвращаемого ответа в функции
(заменить суммирование на минимум/максимум). Поиск минимума/максимума и количества раз, которое он встречается Задача аналогична предыдущей, только теперь помимо максимума требуется также возвращать количество его вхождений. Эта задача встаёт естественным образом, например, при решении с помощью дерева отрезков такой задачи: найти количество наидлиннейших возрастающих подпоследовательностей в заданном массиве. Для решения этой задачи в каждой вершине дерева отрезков будем хранить пару чисел: кроме максимума количество его вхождений на соответствующем отрезке. Тогда при построении дерева мы должны просто по двум таким парам, полученным от сыновей текущей вершины, получать пару для текущей вершины. Объединение двух таких пар в одну стоит выделить в отдельную функцию, поскольку эту операцию надо будет производить и в запросе модификации, и в запросе поиска максимума.
pair<int,int> t[4*MAXN];
pair<int,int> combine (pair<int,int> a, pair<int,int> b) {
if (a.first > b.first)return a;if (b.first > a.first)return b;return make_pair (a.first, a.second + b.second);}
void build (int a[], int v, int tl, int tr) {
if (tl == tr)t[v] = make_pair (a[tl], 1);
else {
int tm = (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];int tm = (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);
else {
int tm = (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]);
} }
Поиск наибольшего общего делителя / наименьшего общего кратного
Т.е. мы хотим научиться искать НОД/НОК всех чисел в заданном отрезке массива. Это довольно интересное обобщение дерева отрезков получается абсолютно таким же путём, как и деревья отрезков для суммы/минимума/максимума: достаточно просто хранить в каждой вершине дерева НОД/НОК всех чисел в соответствующем отрезке массива.
Подсчёт количества нулей, поиск
-го нуля
В этой задаче мы хотим научиться отвечать на запрос количества нулей в заданном отрезке массива, а также на
запрос нахождения
-го нулевого элемента. Снова немного изменим данные, хранящиеся в дереве отрезков: будем хранить теперь в массиве
количество
нулей, встречающихся в соответствующих отрезках массива. Понятно, как поддерживать и использовать эти данные
в функциях
,
,
, — тем самым мы решили задачу о количестве нулей в заданном отрезке массива.
Теперь научимся решать задачу о поиске позиции
-го вхождения нуля в массиве. Для этого будем спускаться по
дереву отрезков, начиная с корня, и переходя каждый раз в левого или правого сына в зависимости от того, в каком
из отрезков находится искомый
-ый ноль. В самом деле, чтобы понять, в какого сына нам надо переходить, достаточно посмотреть на значение, записанное в левом сыне: если оно больше либо равно
, то переходить надо
в левого сына (потому что в его отрезке есть как минимум
нулей), а иначе — переходить в правого сына.
При реализации можно отсечь случай, когда
-го нуля не существует, ещё при входе в функцию, вернув в качестве
ответа, например,
.
int find_kth (int v, int tl, int tr, int k) {if (k > t[v])return -1;if (tl == tr)return tl;int tm = (tl + tr) / 2;if (t[v*2] >= k)return find_kth (v*2, tl, tm, k);else
return find_kth (v*2+1, tm+1, tr, k - t[v*2]);}
Поиск префикса массива с заданной суммой
Задача такая: требуется по данному значению
быстро найти такое
, что сумма первых
элементов массива
больше либо равна
(считая, что массив
содержит только неотрицательные числа). Эту задачу можно решать бинарным поиском, вычисляя каждый раз внутри него сумму на том или ином префиксе
массива, но это приведёт к решению за время
. Вместо этого можно воспользоваться той же самой идеей, что и в предыдущем пункте, и искать искомую позицию одним спуском по дереву: переходя каждый раз в левого или правого сына в зависимости от ве
...
C# решение
auto-draft, проверить перед отправкойusing System;
using System.Collections.Generic;
using System.Linq;
public static class AlgorithmDraft
{
// Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
int n, t[4*MAXN];
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = a[tl];
else {
int tm = (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)
return 0;
if (l == tl && r == tr)
return t[v];
int tm = (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;
else {
int tm = (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];
}
}
pair<int,int> t[4*MAXN];
pair<int,int> combine (pair<int,int> a, pair<int,int> b) {
if (a.first > b.first)
return a;
if (b.first > a.first)
return b;
return make_pair (a.first, a.second + b.second);
}
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = make_pair (a[tl], 1);
else {
int tm = (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];
int tm = (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);
else {
int tm = (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]);
}
}
int find_kth (int v, int tl, int tr, int k) {
if (k > t[v])
return -1;
if (tl == tr)
return tl;
int tm = (tl + tr) / 2;
if (t[v*2] >= k)
return find_kth (v*2, tl, tm, k);
else
return find_kth (v*2+1, tm+1, tr, k - t[v*2]);
}
struct data {
int sum, pref, suff, ans;
};
data combine (data l, data r) {
data res;
res.sum = l.sum + r.sum;
res.pref = max (l.pref, l.sum + r.pref);
res.suff = max (r.suff, r.sum + l.suff);
res.ans = max (max (l.ans, r.ans), l.suff + r.pref);
return res;
}
data make_data (int val) {
data res;
res.sum = val;
res.pref = res.suff = res.ans = max (0, val);
return res;
}
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = make_data (a[tl]);
else {
int tm = (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);
else {
int tm = (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];
int tm = (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)
);
}
List<int> t[4*MAXN];
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = List<int> (1, a[tl]);
else {
int tm = (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]));
}
}
int query (int v, int tl, int tr, int l, int r, int x) {
if (l > r)
return INF;
if (l == tl && tr == r) {
List<int>::iterator pos = lower_bound (t[v].begin(), t[v].
end(), x);
if (pos != t[v].end())
return *pos;
return INF;
}
int tm = (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)
);
}
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) {
int tm = (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;
}
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = a[tl];
else {
int tm = (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;
else {
int tm = (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];
int tm = (tl + tr) / 2;
if (pos <= tm)
return t[v] + get (v*2, tl, tm, pos);
else
return t[v] + get (v*2+1, tm+1, tr, pos);
}
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);
int tm = (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);
int tm = (tl + tr) / 2;
if (pos <= tm)
return get (v*2, tl, tm, pos);
else
return get (v*2+1, tm+1, tr, pos);
}
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][vy];
else {
int my = (ly + ry) / 2;
build_y (vx, lx, rx, vy*2, ly, my);
build_y (vx, lx, rx, vy*2+1, my+1, ry);
t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
}
}
void build_x (int vx, int lx, int rx) {
if (lx != rx) {
int mx = (lx + rx) / 2;
build_x (vx*2, lx, mx);
build_x (vx*2+1, mx+1, rx);
}
build_y (vx, lx, rx, 1, 0, m-1);
}
int sum_y (int vx, int vy, int tly, int try_, int ly, int ry) {
if (ly > ry)
return 0;
if (ly == tly && try_ == ry)
return t[vx][vy];
int tmy = (tly + try_) / 2;
return sum_y (vx, vy*2, tly, tmy, ly, min(ry,tmy))
+ sum_y (vx, vy*2+1, tmy+1, try_, max(ly,tmy+1), ry);
}
int sum_x (int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
if (lx > rx)
return 0;
if (lx == tlx && trx == rx)
return sum_y (vx, 1, 0, m-1, ly, ry);
int tmx = (tlx + trx) / 2;
return sum_x (vx*2, tlx, tmx, lx, min(rx,tmx), ly, ry)
+ sum_x (vx*2+1, tmx+1, trx, max(lx,tmx+1), rx, ly, ry);
}
void update_y (int vx, int lx, int rx, int vy, int ly, int ry, int x, int
y, int new_val) {
if (ly == ry) {
if (lx == rx)
t[vx][vy] = new_val;
else
t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
}
else {
int my = (ly + ry) / 2;
if (y <= my)
update_y (vx, lx, rx, vy*2, ly, my, x, y, new_val);
else
update_y (vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
}
}
void update_x (int vx, int lx, int rx, int x, int y, int new_val) {
if (lx != rx) {
int mx = (lx + rx) / 2;
if (x <= mx)
update_x (vx*2, lx, mx, x, y, new_val);
else
update_x (vx*2+1, mx+1, rx, x, y, new_val);
}
update_y (vx, lx, rx, 1, 0, m-1, x, y, new_val);
}
struct vertex {
vertex * l, * r;
int sum;
vertex (int val)
: l(NULL), r(NULL), sum(val)
{ }
vertex (vertex * l, vertex * r)
: l(l), r(r), sum(0)
{
if (l) sum += l->sum;
if (r) sum += r->sum;
}
};
vertex * build (int a[], int tl, int tr) {
if (tl == tr)
return new vertex (a[tl]);
int tm = (tl + tr) / 2;
return new vertex (
build (a, tl, tm),
build (a, tm+1, tr)
);
}
int get_sum (vertex * t, int tl, int tr, int l, int r) {
if (l > r)
return 0;
if (l == tl && tr == r)
return t->sum;
int tm = (tl + tr) / 2;
return get_sum (t->l, tl, tm, l, min(r,tm))
+ get_sum (t->r, tm+1, tr, max(l,tm+1), r);
}
vertex * update (vertex * t, int tl, int tr, int pos, int new_val) {
if (tl == tr)
return new vertex (new_val);
int tm = (tl + tr) / 2;
if (pos <= tm)
return new vertex (
update (t->l, tl, tm, pos, new_val),
t->r
);
else
return new vertex (
t->l,
update (t->r, tm+1, tr, pos, new_val)
);
}
}C++ решение
сопоставлено/оригиналint n, t[4*MAXN];
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = a[tl];
else {
int tm = (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)
return 0;
if (l == tl && r == tr)
return t[v];
int tm = (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;
else {
int tm = (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];
}
}
pair<int,int> t[4*MAXN];
pair<int,int> combine (pair<int,int> a, pair<int,int> b) {
if (a.first > b.first)
return a;
if (b.first > a.first)
return b;
return make_pair (a.first, a.second + b.second);
}
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = make_pair (a[tl], 1);
else {
int tm = (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];
int tm = (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);
else {
int tm = (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]);
}
}
int find_kth (int v, int tl, int tr, int k) {
if (k > t[v])
return -1;
if (tl == tr)
return tl;
int tm = (tl + tr) / 2;
if (t[v*2] >= k)
return find_kth (v*2, tl, tm, k);
else
return find_kth (v*2+1, tm+1, tr, k - t[v*2]);
}
struct data {
int sum, pref, suff, ans;
};
data combine (data l, data r) {
data res;
res.sum = l.sum + r.sum;
res.pref = max (l.pref, l.sum + r.pref);
res.suff = max (r.suff, r.sum + l.suff);
res.ans = max (max (l.ans, r.ans), l.suff + r.pref);
return res;
}
data make_data (int val) {
data res;
res.sum = val;
res.pref = res.suff = res.ans = max (0, val);
return res;
}
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = make_data (a[tl]);
else {
int tm = (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);
else {
int tm = (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];
int tm = (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)
);
}
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]);
else {
int tm = (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]));
}
}
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;
}
int tm = (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)
);
}
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) {
int tm = (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;
}
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = a[tl];
else {
int tm = (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;
else {
int tm = (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];
int tm = (tl + tr) / 2;
if (pos <= tm)
return t[v] + get (v*2, tl, tm, pos);
else
return t[v] + get (v*2+1, tm+1, tr, pos);
}
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);
int tm = (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);
int tm = (tl + tr) / 2;
if (pos <= tm)
return get (v*2, tl, tm, pos);
else
return get (v*2+1, tm+1, tr, pos);
}
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][vy];
else {
int my = (ly + ry) / 2;
build_y (vx, lx, rx, vy*2, ly, my);
build_y (vx, lx, rx, vy*2+1, my+1, ry);
t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
}
}
void build_x (int vx, int lx, int rx) {
if (lx != rx) {
int mx = (lx + rx) / 2;
build_x (vx*2, lx, mx);
build_x (vx*2+1, mx+1, rx);
}
build_y (vx, lx, rx, 1, 0, m-1);
}
int sum_y (int vx, int vy, int tly, int try_, int ly, int ry) {
if (ly > ry)
return 0;
if (ly == tly && try_ == ry)
return t[vx][vy];
int tmy = (tly + try_) / 2;
return sum_y (vx, vy*2, tly, tmy, ly, min(ry,tmy))
+ sum_y (vx, vy*2+1, tmy+1, try_, max(ly,tmy+1), ry);
}
int sum_x (int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
if (lx > rx)
return 0;
if (lx == tlx && trx == rx)
return sum_y (vx, 1, 0, m-1, ly, ry);
int tmx = (tlx + trx) / 2;
return sum_x (vx*2, tlx, tmx, lx, min(rx,tmx), ly, ry)
+ sum_x (vx*2+1, tmx+1, trx, max(lx,tmx+1), rx, ly, ry);
}
void update_y (int vx, int lx, int rx, int vy, int ly, int ry, int x, int
y, int new_val) {
if (ly == ry) {
if (lx == rx)
t[vx][vy] = new_val;
else
t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
}
else {
int my = (ly + ry) / 2;
if (y <= my)
update_y (vx, lx, rx, vy*2, ly, my, x, y, new_val);
else
update_y (vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
}
}
void update_x (int vx, int lx, int rx, int x, int y, int new_val) {
if (lx != rx) {
int mx = (lx + rx) / 2;
if (x <= mx)
update_x (vx*2, lx, mx, x, y, new_val);
else
update_x (vx*2+1, mx+1, rx, x, y, new_val);
}
update_y (vx, lx, rx, 1, 0, m-1, x, y, new_val);
}
struct vertex {
vertex * l, * r;
int sum;
vertex (int val)
: l(NULL), r(NULL), sum(val)
{ }
vertex (vertex * l, vertex * r)
: l(l), r(r), sum(0)
{
if (l) sum += l->sum;
if (r) sum += r->sum;
}
};
vertex * build (int a[], int tl, int tr) {
if (tl == tr)
return new vertex (a[tl]);
int tm = (tl + tr) / 2;
return new vertex (
build (a, tl, tm),
build (a, tm+1, tr)
);
}
int get_sum (vertex * t, int tl, int tr, int l, int r) {
if (l > r)
return 0;
if (l == tl && tr == r)
return t->sum;
int tm = (tl + tr) / 2;
return get_sum (t->l, tl, tm, l, min(r,tm))
+ get_sum (t->r, tm+1, tr, max(l,tm+1), r);
}
vertex * update (vertex * t, int tl, int tr, int pos, int new_val) {
if (tl == tr)
return new vertex (new_val);
int tm = (tl + tr) / 2;
if (pos <= tm)
return new vertex (
update (t->l, tl, tm, pos, new_val),
t->r
);
else
return new vertex (
t->l,
update (t->r, tm+1, tr, pos, new_val)
);
}Java решение
auto-draft, проверить перед отправкойimport java.util.*;
import java.math.*;
public class AlgorithmDraft {
// Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
int n, t[4*MAXN];
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = a[tl];
else {
int tm = (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)
return 0;
if (l == tl && r == tr)
return t[v];
int tm = (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;
else {
int tm = (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];
}
}
pair<int,int> t[4*MAXN];
pair<int,int> combine (pair<int,int> a, pair<int,int> b) {
if (a.first > b.first)
return a;
if (b.first > a.first)
return b;
return make_pair (a.first, a.second + b.second);
}
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = make_pair (a[tl], 1);
else {
int tm = (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];
int tm = (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);
else {
int tm = (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]);
}
}
int find_kth (int v, int tl, int tr, int k) {
if (k > t[v])
return -1;
if (tl == tr)
return tl;
int tm = (tl + tr) / 2;
if (t[v*2] >= k)
return find_kth (v*2, tl, tm, k);
else
return find_kth (v*2+1, tm+1, tr, k - t[v*2]);
}
struct data {
int sum, pref, suff, ans;
};
data combine (data l, data r) {
data res;
res.sum = l.sum + r.sum;
res.pref = max (l.pref, l.sum + r.pref);
res.suff = max (r.suff, r.sum + l.suff);
res.ans = max (max (l.ans, r.ans), l.suff + r.pref);
return res;
}
data make_data (int val) {
data res;
res.sum = val;
res.pref = res.suff = res.ans = max (0, val);
return res;
}
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = make_data (a[tl]);
else {
int tm = (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);
else {
int tm = (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];
int tm = (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)
);
}
ArrayList<Integer> t[4*MAXN];
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = ArrayList<Integer> (1, a[tl]);
else {
int tm = (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]));
}
}
int query (int v, int tl, int tr, int l, int r, int x) {
if (l > r)
return INF;
if (l == tl && tr == r) {
ArrayList<Integer>::iterator pos = lower_bound (t[v].begin(), t[v].
end(), x);
if (pos != t[v].end())
return *pos;
return INF;
}
int tm = (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)
);
}
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) {
int tm = (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;
}
void build (int a[], int v, int tl, int tr) {
if (tl == tr)
t[v] = a[tl];
else {
int tm = (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;
else {
int tm = (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];
int tm = (tl + tr) / 2;
if (pos <= tm)
return t[v] + get (v*2, tl, tm, pos);
else
return t[v] + get (v*2+1, tm+1, tr, pos);
}
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);
int tm = (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);
int tm = (tl + tr) / 2;
if (pos <= tm)
return get (v*2, tl, tm, pos);
else
return get (v*2+1, tm+1, tr, pos);
}
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][vy];
else {
int my = (ly + ry) / 2;
build_y (vx, lx, rx, vy*2, ly, my);
build_y (vx, lx, rx, vy*2+1, my+1, ry);
t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
}
}
void build_x (int vx, int lx, int rx) {
if (lx != rx) {
int mx = (lx + rx) / 2;
build_x (vx*2, lx, mx);
build_x (vx*2+1, mx+1, rx);
}
build_y (vx, lx, rx, 1, 0, m-1);
}
int sum_y (int vx, int vy, int tly, int try_, int ly, int ry) {
if (ly > ry)
return 0;
if (ly == tly && try_ == ry)
return t[vx][vy];
int tmy = (tly + try_) / 2;
return sum_y (vx, vy*2, tly, tmy, ly, min(ry,tmy))
+ sum_y (vx, vy*2+1, tmy+1, try_, max(ly,tmy+1), ry);
}
int sum_x (int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
if (lx > rx)
return 0;
if (lx == tlx && trx == rx)
return sum_y (vx, 1, 0, m-1, ly, ry);
int tmx = (tlx + trx) / 2;
return sum_x (vx*2, tlx, tmx, lx, min(rx,tmx), ly, ry)
+ sum_x (vx*2+1, tmx+1, trx, max(lx,tmx+1), rx, ly, ry);
}
void update_y (int vx, int lx, int rx, int vy, int ly, int ry, int x, int
y, int new_val) {
if (ly == ry) {
if (lx == rx)
t[vx][vy] = new_val;
else
t[vx][vy] = t[vx*2][vy] + t[vx*2+1][vy];
}
else {
int my = (ly + ry) / 2;
if (y <= my)
update_y (vx, lx, rx, vy*2, ly, my, x, y, new_val);
else
update_y (vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
t[vx][vy] = t[vx][vy*2] + t[vx][vy*2+1];
}
}
void update_x (int vx, int lx, int rx, int x, int y, int new_val) {
if (lx != rx) {
int mx = (lx + rx) / 2;
if (x <= mx)
update_x (vx*2, lx, mx, x, y, new_val);
else
update_x (vx*2+1, mx+1, rx, x, y, new_val);
}
update_y (vx, lx, rx, 1, 0, m-1, x, y, new_val);
}
struct vertex {
vertex * l, * r;
int sum;
vertex (int val)
: l(NULL), r(NULL), sum(val)
{ }
vertex (vertex * l, vertex * r)
: l(l), r(r), sum(0)
{
if (l) sum += l->sum;
if (r) sum += r->sum;
}
};
vertex * build (int a[], int tl, int tr) {
if (tl == tr)
return new vertex (a[tl]);
int tm = (tl + tr) / 2;
return new vertex (
build (a, tl, tm),
build (a, tm+1, tr)
);
}
int get_sum (vertex * t, int tl, int tr, int l, int r) {
if (l > r)
return 0;
if (l == tl && tr == r)
return t->sum;
int tm = (tl + tr) / 2;
return get_sum (t->l, tl, tm, l, min(r,tm))
+ get_sum (t->r, tm+1, tr, max(l,tm+1), r);
}
vertex * update (vertex * t, int tl, int tr, int pos, int new_val) {
if (tl == tr)
return new vertex (new_val);
int tm = (tl + tr) / 2;
if (pos <= tm)
return new vertex (
update (t->l, tl, tm, pos, new_val),
t->r
);
else
return new vertex (
t->l,
update (t->r, tm+1, tr, pos, new_val)
);
}
}Материал разбит как алгоритмическая задача: изучить постановку, понять асимптотику и реализовать алгоритм на выбранном языке.
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.