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

Материал из Algocode wiki
Перейти к: навигация, поиск

Дерево Фенвика — структура данных, умеющая решать задачу RSQ с обновлением. Ее можно решать и деревом отрезков, но Фенвик в разы быстрее с точки зрения константы и пишется в пару строк.

Идея

Замечание. Искать с помощью дерева Фенвика будем только сумму на префиксе, а RSQ считать будем префиксными суммами

Замечание_1. Из-за тонкостей итоговой реализации решать задачу будем в 1-индексации.

Мы будем хранить массив $f[MAXN]$ такой, что $$f_i = \sum_{k = F(i)}^{i} a_k$$ Функцию $F(i)$ определим позже.

Тогда запрос суммы определяется так: $$ sum(i) = \begin{cases} 0 &\mbox{if } i = 0 \\ f_i + sum(F(i) - 1) &\mbox{if } i \neq 0 \end{cases} $$

А для запроса обновления надо изменить все ячейки, в которых учтен $a_i$

Выбор формулы. Возьмем $F(x) = x - (x \& -x) + 1$. Замечание. Выражение $x \& -x$ возвращает последний бит в записи числа x. (поэтому мы решаем в 1-индексации).

Очевидно, что get-запрос

  • Работает корректно
  • Работает за $O(\log n)$, тк каждый раз удаляет один бит у числа

Что делать с update-запросами? Надо понять, какие вершины надо обновить, если мы изменили элемент $v$. Ответ — такие $x$, что $F(x) \le v \le x$. Что это за числа, на самом деле? Такие, которые больше, чем наше $v$, но без последнего бита они уже меньше. Это значит, что все биты числа $x$, кроме последнего, встречаются в числе $v$. Кроме того, те биты, которые встречаются в $v$, но не встречаются в $x$, находятся правее последней единицы в $x$. То есть у $v$ и $x$ есть общий префикс битов, а потом в $x$ стоят $10\ldots00$, а в $v$ стоит 0, а потом что угодно.

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

 1 int f[MAXN];
 2 void upd(int x, int add) {
 3     for (int i = x; i < MAXN; i += i & -i) {
 4         f[i] += add;
 5     }
 6 }
 7 
 8 int get(int x) {
 9     int res = 0;
10     for (int i = x; i > 0; i -= i & -i) {
11          res += f[i];
12     }
13     return res;
14 }

Реализация с альтернативными функциями:

 1 int t[MAXN];
 2 void upd(int x, int add) {
 3     for (int i = x; i < MAXN; i = i | (i + 1)) {
 4         f[i] += add;
 5     }
 6 }
 7 
 8 int get(int x) {
 9     int res = 0;
10     for (int i = x; i > 0; i = (i & (i + 1)) - 1) {
11          res += f[i];
12     }
13     return res;
14 }


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

Аналогично многомерному дереву отрезков, многомерный Фенвик — это Фенвик по Фенвику по $\ldots$ по Фенвику. Отличие от предыдущего кода только в размерности массива и количестве циклов.

 1 void upd(int x, int y, int add) {
 2     for (int i = x; i < MAXN; i += i & -i) {
 3         for (int j = y; j < MAXN; j += j & -j) {
 4             f[i][j] += add;
 5         }
 6     }
 7 }
 8 
 9 int get(int x, int y) {
10     int res = 0;
11     for (int i = x; i > 0; i -= i & -i) {
12         for (int j = y; j > 0; j -= j & -j) {
13             res += f[i][j];
14         }
15     }
16     return res;
17 }

Реализация с альтернативными функциями:

 1 void upd(int x, int y, int add) {
 2     for (int i = x; i < MAXN; i = i | (i + 1)) {
 3         for (int j = y; j < MAXN; j = j | (j + 1)) {
 4             f[i][j] += add;
 5         }
 6     }
 7 }
 8 
 9 int get(int x, int y) {
10     int res = 0;
11     for (int i = x; i > 0; i = (i & (i + 1)) - 1) {
12         for (int j = y; j > 0; j = (j & (j + 1)) - 1) {
13             res += f[i][j];
14         }
15     }
16     return res;
17 }

Динамический Фенвик

Если массив достаточно большой, то можно хранить Фенвика в $std::map$ или $std::unordered\_map$, и делать с ним те же самые операции, что и раньше. Идея точно такая же, как и в случае неявного дерева отрезков

Спуск по Фенвику

Мы умеем делать спуск по дереву отрезков. Как сделать то же самое для Фенвика? Зная, что $f_i$ хранит сумму на отрезке от $i$ до $i$ без младшего бита, становится понятно, что можно делать спуск так:

  • Итерироваться по степеням двойки сверху вниз и поддерживать текущее $pos$
  • Если $f_{pos + 2^i} < s$, то мы делаем прыжок от $pos$ к $pos + 2^i$ и уменьшаем $s$ (ведь $f_{pos + 2^i} = \sum_{k=pos + 1}^{pos + 2^i} a_k$).
 1 int find_last_less (int s) {
 2     int k = 0;
 3     for (int l = logn; l >= 0; l--) {
 4         if (k + (1 << l) <= n && f[k + (1<<l)] < s) {
 5             k += (1 << l);
 6             s -= f[k];
 7         }
 8     }
 9     return k;
10 }



Автор конспекта: Константин Амеличев

По всем вопросам пишите в telegram @kik0s


Автор конспекта: Саша Гришутин

По всем вопросам пишите в telegram @rationalex