Дерево Фенвика
Дерево Фенвика — структура данных, умеющая решать задачу 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$).
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 [Категория:Структуры данных для запросов на отрезке]