Дерево фенвика дерево отрезков

Дерево Фенвика с модификацией на отрезке

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

1. Постановка задачи

1. Модификация — прибавить d к каждому элементу отрезка [l, r]
2. Сумма — вычислить сумму элементов отрезка [l, r]

2. Описание решения

Нетрудно заметить, что оба вида запросов можно «облегчить» до отрезка [0, r], разбивая отрезок [l, r] на два префикса. Как и для дерева отрезков, заведём второй массив, в котором будем хранить сколько надо прибавить ко всем числам этого отрезка.

Создадим класс Fenwick с прототипами будущих методов.

В первом конструкторе достаточно выделить память и обнулить элементы массива. А во втором ещё пройдёмся по массиву a и прорелаксируем значения в дереве.

Fenwick::Fenwick(int n) < N = n; m = new int[N]; mt = new int[N]; memset(m, 0, sizeof(int)*N); memset(mt, 0, sizeof(int)*N); >Fenwick::Fenwick(int a[], int n) < N = n; m = new int[N]; mt = new int[N]; memset(m, 0, sizeof(int)*N); memset(mt, 0, sizeof(int)*N); for(int i=0;i> 

Рассмотрим теперь операцию изменения. Предположим пришёл запрос «прибавить 1 к элементам отрезка [0, 9]». Этот отрезок полностью покрывается непересекающимися отрезками [0, 7] и [8, 9], поэтому в 7 и 9 элементы массива mt прибавляем 1. Но есть отрезки, содержащие [0, 9] (или его часть) в качестве подотрезка. Все они располагаются справа. Для них необходимо изменить значение в массиве m на столько, сколько элементов отрезка [0, 9] они содержат. То есть в m[11] прибавить 2, а к m[15] — 10.

Из рисунка видно, что перемещения происходят по тем же законам, что и в тривиальной реализации дерева Фенвика, поэтому сразу перейдём к коду.

void Fenwick::add_range(int r, int d)< if(r<0) return ; for(int i=r;i>=0;i=(i&(i+1))-1) mt[i] += d; for(int i=r|(r+1);i void Fenwick::add_range(int l, int r, int d)

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

int Fenwick::sum(int r)< if(r<0) return 0; int res = 0; for(int i=r;i>=0;i=(i&(i+1))-1) res += m[i] + mt[i]*(i-(i&(i+1))+1); for(int i=r|(r+1);i int Fenwick::sum(int l, int r)

3. Итоги

Нам удалось получить структуру данных с инициализацией за O(N), модификацией и суммой на отрезке за O(logN). На рандомном тесте с 10000000 элементов и 10000000 запросов получил такие цифры:

Структура данных	Инициализация	Модификация	Сумма
Fenwick	0.13 с	9.12 с	8.90 с
RSQ (реализация с e-maxx)	0.25 с	17.13 с	13.53 с

Источник

Дерево Фенвика

Дерево Фенвика или двоичное индексированное дерево (англ. binary indexed tree) — структура данных, которая на многих задачах заменяет собой дерево отрезков, но при этом работает в 3-4 раза быстрее, занимает минимально возможное количество памяти (столько же, сколько и массив той же длины), намного быстрее пишется и легче обобщается на большие размерности.

#Определение

Пусть дан массив $a$ длины $n$. Деревом Фенвика будем называть массив $t$ той же длины, объявленный следующим образом:

где $F$ это какая-то функцию, для которой выполнено $F(i) \leq i$. Конкретно её определим потом.

Запрос суммы. Когда нам нужна сумма на отрезке, мы будем сводить этот запрос к двум суммам на префиксе:

$$ sum(l, r) = sum(r) — sum(l-1) $$ Оба этих запроса будем считать по формуле: $$ sum(k) = t_k + sum(F(k)-1) $$

Запрос обновления. Когда мы изменяем $k$-ю ячейку исходного массива, мы обновляем все $t_i$, в которых учтена эта ячейка.

$F$ можно выбрать так, что и «спусков» при подсчете суммы, и интересных нам $t_i$ при обновлении будет будет $O(\log n)$. Популярны две функции:

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

Примечание. Наверное, меньше четверти умеющих писать эту структуру полностью понимают, как она работает. Анализ действительно весьма сложный, поэтому мы приведём его в конце. Рекомендуется пока что абстрагироваться и принять на веру, что любой префикс разбивается на $O(\log n)$ отрезков вида $[F(i), i]$, а также что любой элемент входит в не более $O(\log n)$ таких отрезков.

#Реализация

Так как $F(0) = 1 > 0$, то $[0, F(0)]$ не является корректным отрезком. Поэтому нам будет удобнее хранить массив в 1-индексации и не использовать $t_0$.

  Автор отмечает красивую симметрию в формулах r -= r & -r и k += k & -k , которой нет в «традиционной» версии.

#Многомерный случай

$k$-мерное дерево Фенвика пишется в $(k+1)$ строчку

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

sum перепишется следующим образом:

В $k$-мерном случае, в соответствии с принципом включений-исключений, для запроса суммы нужно $2^k$ запросов суммы на префиксах.

Если размерности больше, чем позволяет память, то можно вместо массива t использовать хеш-таблицу — так потенциально потребуется $O(q \log^2 A)$ памяти ($A$ — максимальная координата), но это всё равно один из самых безболезненных способов решать достаточно простые задачи на двумерные структуры.

#Бинпоиск

Оказывается, можно производить бинарный поиск (точнее, спуск) по префиксным суммам за $O(\log n)$.

 Если знать, что $F(x)$ удаляет последний бит $x$, то принцип понятен: просто делаем спуск по бинарному дереву, как в ДО. Чем-то похоже на генерацию $k$-го лексикографического комбинаторного объекта: пытаемся увеличить следующий символ всегда, когда это возможно.

Отметим, что в «традиционной» индексации такое делать нельзя.

#Ограничения на операцию

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

#Почему это работает

Итак, мы выбрали вариант с $F(x)$ = x — (x & -x) + 1 . Поймем, что означает x & -x .

Лемма. x & -x возвращает последний единичный бит в двоичной записи x.

Доказательство потребует знания, как в компьютерах хранятся целые числа. Чтобы процессор не сжигал лишние такты, проверяя знак числа при арифметических операциях, их хранят как бы по модулю $2^k$, а первый бит отвечает за знак (0 для положительных и 1 для отрицательных). Поэтому когда мы хотим узнать, как выглядит отрицательное число, нужно его вычесть из нуля: $-x = 0-x = 2^k-x$.

Как будет выглядеть -x в битовой записи? Ответ можно мысленно разделить на три блока:

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

$$ \begin +90 = 2+8+16+64 & = 0 \, 10110_2 \\ -90 = 00000_2 — 10110_2 & = 1 \, 01010_2 \\ \implies (+90) \& (-90) & = 0 \, 00010_2 \end $$

Теперь мы можем доказать нашу лемму. Когда мы сделаем &, в префиксе до младшего единичного бита все биты x и -x будут противоположными, младший единичный бит останется единичным, а на суффиксе все как было нулями, так и осталось. Следовательно, «выживет» только этот самый младший единичный бит, что мы и доказывали.

Следствие 1. sum будет работать за логарифм, а точнее за количество единичных битов в записи $x$: на каждой итерации мы делаем x -= x & -x , то есть удаляем младший бит.

Следствие 2. add тоже будет работать за логарифм: каждую итерацию количество нулей на конце $x$ увеличивается хотя бы на единицу.

Следствие 3. (Почему дерево Фенвика — дерево.)

• Длина отрезка, соответствующего любому $t_i$ — степень двойки, причём начинается этот отрезок на индексе, кратном этой же степени двойки.
• $\implies$ Множества элементов, учтённых в произвольных $t_i$ и $t_j$, либо не пересекаются, либо одно является подмножеством другого.
• $\implies$ На $t_i$ можно ввести отношение вложенности.

То есть, если напрячь воображение, то $t$ можно рассматривать как лес деревьев. В частном случае, когда $n$ является степенью двойки, дерево будет одно.

Теперь единственное, что осталось доказать ­— это корректность add . На самом деле, в add мы делаем ни что иное, как подъём от вершины до корня по всем предкам.

Как для $x$ найти непосредственного родителя? Нужно найти минимальное число $y > x$, у которого $t_y$ будет включать $x$. Иными словами, должно выполняться y >= x > y — (y & -y) .

Дальше читателю предлагается самостоятельно попялиться в пример, чтобы понять, что x + (x & -x) — минимальное такое число:

$$ \begin x = 90 = 2+8+16+64 & = 10110_2 \\\ y = 96 = 32 + 64 & = 11000_2 \end $$

Источник