Дерево отрезков снизу
Дерево отрезков — крайне функциональная структура данных, с помощью которой можно решить огромное количество задач. Однако оно достаточно медленное: производятся рекурсивные вызовы и тому подобное. Иногда это приводит к тому, что решение может не проходить по времени. Кроме того, стандартное дерево отрезков — это не самый очевидный для написания алгоритм.
Чтобы решить эти проблемы часто прибегают к использованию дерева Фенвика. Оно очень простое в реализации, очень быстро работает, а также его легко обобщать для бóльших размерностей. Однако оно ограничено тем, что в своей базовой вариации оно подходит только для обратимых операций, потому что считает функцию на отрезке через два префикса. То есть, к примеру, минимум на отрезке стандартным деревом Фенвика посчитать не получится. Кроме того, стандартное дерево Фенвика поддерживает изменение только в точке, но не на отрезке. В таких ситуациях вам может захотеться прибегнуть к использованию дерева отрезков снизу. Это нерекурсивная структура данных, которая одновременно работает так же быстро, как и дерево Фенвика, и при этом так же (или почти) функциональна как обычное дерево отрезков.
Изменение в точке, сумма на отрезке
Идея скрывается в названии. Если в обычном дереве отрезков мы начинаем с корня и идем вниз, разбивая отрезок запроса на логарифм подотрезков, то в дереве отрезков снизу мы начинаем с листьев и поднимаемся вверх.
Для начала давайте дополним длину массива до ближайшей степени двойки, чтобы он полностью лежал на одном уровне дерева. От этого асимптотика никак не поменяется.
Давайте сначала рассмотрим базовую задачу. Есть запросы двух видов: изменить значение в точке и найти сумму на отрезке.
Изменение в точке реализуется очень просто. Мы изменяем значение в листе, соответствующем этой точке, а затем постепенно идем до корня, обновляя значения в вершинах на пути через значения в детях.
Поиск суммы на отрезке тоже весьма прост. Вместо того, чтобы суммировать отрезок из $k$ значений на текущем уровне, мы можем перейти на предыдущий уровень и там просуммировать лишь $\frac{k}{2}$ значений, ведь элементы более высокого уровня отвечают за сумму двух соседних элементов текущего уровня. Однако если левая граница отрезка является правым сыном, либо правая граница является левым сыном, то мы не можем перейти для них на предыдущий уровень, и их значения надо прибавить на текущем этапе. Так мы будем постепенно подниматься по дереву, делая на каждом уровне константное количество операций.
Асимптотика изменения равна $O(\log n)$, потому что состоит просто из прохода от листа к корню, а асимптотика нахождения суммы на полуинтервале $[l, r)$ равна $O(\log (r - l))$, что в общем случае, конечно, равно $O(\log n)$.
Построение дерева выглядит совсем просто. Мы записываем элементы изначального массива в листья подряд, а затем проходим по внутренним вершинам по убыванию, пересчитывая значение текущей вершины через детей.
const int N = (1 << 20); // N = 2^k, N >= n
long long tree[2 * N];
void build(const vector<int>& arr) {
for (size_t i = 0; i < arr.size(); i++) {
tree[N + i] = arr[i];
}
for (int i = N - 1; i > 0; i--) {
tree[i] = tree[i << 1] + tree[(i << 1) | 1];
}
}
void updatePoint(int pos, int newval) { // arr[pos] := newval
pos += N;
tree[pos] = newval;
pos >>= 1;
while (pos > 0) {
tree[pos] = tree[pos << 1] + tree[(pos << 1) | 1];
pos >>= 1;
}
}
long long find_sum(int l, int r) { // [l, r)
l += N;
r += N;
long long ans = 0;
while (l < r) {
if (l & 1) {
ans += tree[l++];
}
if (r & 1) {
ans += tree[--r];
}
l >>= 1;
r >>= 1;
}
return ans;
}
Мы заменили все операции на битовые для ускорения. Отец вершины v — это v >> 1, а сыновья — v << 1 и (v << 1) | 1. Вершина является правым сыном, если ее номер нечетный, а левым, если четный (обратите внимание, что и для левой, и для правой границы условия в find_sum одинаковые, потому что правая граница берется не включительно).
Однако самое удивительное — это то, что на самом деле везде в этом коде вместо N можно написать n:
vector<long long> tree;
int n;
void build(const vector<int>& arr) {
n = arr.size();
tree.assign(2 * n, 0);
for (int i = 0; i < n; i++) {
tree[n + i] = arr[i];
}
for (int i = n - 1; i > 0; i--) {
tree[i] = tree[i << 1] + tree[(i << 1) | 1];
}
}
void update_point(int pos, int newval) { // arr[pos] := newval
pos += n;
tree[pos] = newval;
pos >>= 1;
while (pos > 0) {
tree[pos] = tree[pos << 1] + tree[(pos << 1) | 1];
pos >>= 1;
}
}
long long find_sum(int l, int r) { // [l, r)
l += n;
r += n;
long long ans = 0;
while (l < r) {
if (l & 1) {
ans += tree[l++];
}
if (r & 1) {
ans += tree[--r];
}
l >>= 1;
r >>= 1;
}
return ans;
}
Замечание: Если вам нужно работать с некоммутативной операцией, то нужно комбинировать ответ правильно. Нужно отдельно хранить левый префикс ответа и правый суффикс, а в конце их объединять.
Таким образом, наша структура будет занимать ровно $2n$ памяти в отличие от обычного дерева отрезков, которому в зависимости от реализации бывает нужно от $4n$ до $8n$ памяти.
Конечно, для операции суммы можно использовать и дерево Фенвика, но так как у нас есть вся мощь дерева отрезков, мы можем считать практически любую другую функцию на отрезке. К примеру, минимум, с которым стандартное дерево Фенвика не справится.
Изменение на отрезке, значение в точке
Как обычно, структуру, которая умеет изменять в точке и находить значение функции на отрезке, можно переделать в структуру, которая умеет изменять целый отрезок и находить значение в точке. Для этого нам надо просто поменять местами функцию изменения с функцией нахождения значения. Функция изменения теперь разобьет отрезок запроса на логарифм вершин дерева отрезков, в каждой из которых она оставит изменение, которое нужно сделать со всем поддеревом. Функция нахождения значения в точке в свою очередь пройдется по пути до корня и посчитает ответ.
Замечание: Обратите внимание, что в этом случае нам необходимо, чтобы операции изменения на отрезке были коммутативны, то есть порядок их применения был неважен. К примеру, для операции прибавления на отрезке это верно, а для операции присвоения на отрезке это неверно. Дело в том, что мы оставляем изменения в вершинах дерева, а когда пытаемся найти значение, идем по порядку по вершинам, но изменения в них могут быть перемешаны во времени. Конкретно для присвоения на отрезке можно кроме самого присвоения хранить еще и момент времени, когда оно было сделано, а потом выбрать максимум таких моментов, однако в общем случае, возможно, что все операции придется применить в правильном порядке, и тогда нам придется их отсортировать, поэтому запрос нахождения значения в точке будет работать за $O(\log n \cdot \log \log n)$. Для некоммутативных операций нам подойдет дерево отрезков с ленивыми обновлениями, которое мы обсудим позже.
vector<long long> tree;
int n;
void build(const vector<int>& arr) {
n = arr.size();
tree.assign(2 * n, 0);
for (int i = 0; i < n; i++) {
tree[n + i] = arr[i];
}
// tree[0..n-1] are zeros because there's nothing to add on a segment
}
long long find_value(int pos) {
pos += n;
long long ans = 0;
while (pos > 0) {
ans += tree[pos];
pos >>= 1;
}
return ans;
}
void segment_update(int l, int r, int addval) { // [l, r)
l += n;
r += n;
while (l < r) {
if (l & 1) {
tree[l++] += addval;
}
if (r & 1) {
tree[--r] += addval;
}
l >>= 1;
r >>= 1;
}
}
Обратите внимание, что в 11 строке мы не пересчитываем значение в вершине через детей, потому что теперь мы в вершине храним не сумму на отрезке, а значение, которое нужно прибавить ко всем числам на отрезке.
Двумерные запросы
Когда дерево отрезков двумерное, оно становится совсем медленным, и нам нужно делать сложную схему из рекурсивного запуска запроса к одномерному дереву отрезков из двумерного. В случае нерекурсивной реализации дерева отрезков снизу все практически так же просто, как с деревом Фенвика. Необходимо лишь написать два вложенных цикла вместо одного:
long long find_sum(int lx, int rx, int ly, int ry) { // [lx, rx) * [ly, ry)
lx += n;
rx += n;
long long ans = 0;
while (lx < rx) {
int curly = ly + m;
int curry = ry + m;
while (curly < curry) {
if (curly & 1) {
if (lx & 1) {
ans += tree[lx][curly];
}
if (rx & 1) {
ans += tree[rx - 1][curly];
}
}
if (curry & 1) {
if (lx & 1) {
ans += tree[lx][curry - 1];
}
if (rx & 1) {
ans += tree[rx - 1][curry - 1];
}
}
curly = (curly + 1) >> 1;
curry >>= 1;
}
lx = (lx + 1) >> 1;
rx >>= 1;
}
return ans;
}
Нужно сдвинуть границу в том случае, если она нечетна и по $x$ координате, и по $y$.
С полной реализацией можно ознакомиться по ссылке.
Ленивые обновления
Чаще всего так получается, что обычно хватает обновления в точке. Либо же если все-таки нужно обновление на отрезке, то ограничения не такие жестокие, и можно использовать обычное дерево отрезков. Однако давайте все-таки поймем, как с помощью дерева отрезков снизу можно поддерживать изменения на отрезке и запрос поиска на отрезке. В этом нам помогут (как и в обычном дереве отрезков) ленивые обновления.
Мы будем поддерживать все то же самое, что и в обычном дереве отрезков, но нужно просто перевести это на язык дерева отрезков снизу.
Когда мы делаем запрос поиска на отрезке, нам нужно протолкнуть отложенные изменения из всех предков вершин, которые мы посетим. Все эти вершины — это просто предки листьев, соответствующих концам отрезка запроса. Однако проталкивать изменения надо сверху вниз, чтобы они комбинировались друг с другом. Как же это сделать в дереве отрезков снизу? Мы знаем, что предок вершины $v$ — это $\left\lfloor \frac{v}{2} \right\rfloor$, тогда $k$-й предок — это $\left\lfloor \frac{v}{2^k} \right\rfloor$. Поэтому мы можем просто перебрать степень двойки по убыванию и проталкивать изменения сверху вниз.
Запрос изменения на отрезке будет выглядеть так же, как запрос поиска суммы на отрезке, только в конце после того как мы изменили какие-то значения, нужно пересчитать значения предков измененных вершин. Но это как и в прошлом случае просто предки листьев, отвечающих за концы отрезка. Однако в этот раз перебирать их надо уже как обычно — снизу вверх.
Также стоит обратить внимание на то, что для вершин с номерами $[n, 2n)$ не нужно хранить ленивые обновления, потому что они являются листьями, поэтому в случае жестких ограничений по памяти можно достичь использования $3n$ ячеек.
Рассмотрим код на примере задачи прибавления на отрезке и поиска максимума на отрезке:
const long long INF = 1e18;
vector<long long> tree;
vector<long long> push;
int n;
int logn;
void build(const vector<int>& arr) {
n = arr.size();
logn = 32 - __builtin_clz(2 * n);
tree.assign(2 * n, 0);
push.assign(n, 0);
for (int i = 0; i < n; i++) {
tree[n + i] = arr[i];
}
for (int i = n - 1; i > 0; i--) {
tree[i] = max(tree[i << 1], tree[(i << 1) | 1]);
}
}
void update_vertex(int v, long long val) {
tree[v] += val;
if (v < n) {
push[v] += val;
}
}
void update_ancestors(int v) {
v >>= 1;
while (v > 0) {
tree[v] = max(tree[v << 1], tree[(v << 1) | 1]) + push[v];
v >>= 1;
}
}
void do_push(int leaf) {
for (int k = logn; k > 0; k--) {
int v = (leaf >> k);
update_vertex(v << 1, push[v]);
update_vertex((v << 1) | 1, push[v]);
push[v] = 0;
}
}
void update_segment(int l, int r, int val) { // [l, r) += val
l += n;
r += n;
int ql = l, qr = r;
while (l < r) {
if (l & 1) {
update_vertex(l++, val);
}
if (r & 1) {
update_vertex(--r, val);
}
l >>= 1;
r >>= 1;
}
update_ancestors(ql);
update_ancestors(qr - 1);
}
long long find_max(int l, int r) { // [l, r)
l += n;
r += n;
do_push(l);
do_push(r - 1);
long long ans = -INF;
while (l < r) {
if (l & 1) {
ans = max(ans, tree[l++]);
}
if (r & 1) {
ans = max(ans, tree[--r]);
}
l >>= 1;
r >>= 1;
}
return ans;
}
В более сложных случаях (к примеру, поиска суммы на отрезке) для пересчета значения в функции apply может понадобиться длина отрезка текущей вершины. И в случае, когда мы идем снизу вверх, и в случае, когда мы идем сверху вниз, легко поддерживать эту величину.
Задачи для практики
Можно потренироваться в первую очередь на любых задачах на дерево отрезков, коих существует бесчисленное количество.
К примеру, можно воспользоваться следующими задачами:
-
Задача на поиск максимума на отрезке.
-
Задача на прибавление на отрезке, присвоение на отрезке и поиск суммы на отрезке.
-
Задача на прибавление арифметической прогрессии на отрезке.
-
Чуть более продвинутая задача на дерево отрезков.
-
ОСТОРОЖНО! СПОЙЛЕРЫ К РОИ! Эту задачу можно очень просто сдать на высокий балл при помощи дерева отрезков снизу. Такое решение выигрывает у разреженных таблиц не смотря на то, что они отвечают на запрос за $O(1)$.