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

Материал из Algocode wiki
Версия от 17:52, 18 сентября 2019; KiKoS (обсуждение | вклад) (code + category)
Перейти к: навигация, поиск

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

Идея

Замечание. Искать с помощью дерева Фенвика будем только сумму на префиксе, а RSQ считать будем префиксными суммами Замечание_1. Из-за тонкостей итоговой реализации решать задачу будем в 1-индексаци.

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

Тогда запрос суммы определяется так: $$sum(i) = f_i + sum(F(i) - 1)$$

А для запроса обновления надо изменить все ячейки, в которых учтен $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 }

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

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

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

Если массив достаточно большой, то можно хранить Фенвика в $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$).



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

По всем вопросам пишите в telegram @kik0s [Категория:Структуры данных для запросов на отрезке]