Дерево Фенвика: различия между версиями
KiKoS (обсуждение | вклад) м |
|||
Строка 38: | Строка 38: | ||
int get(int x) { | int get(int x) { | ||
int res = 0; | int res = 0; | ||
− | for (int i = x; i > 0; i = | + | for (int i = x; i > 0; i -= i & -i) { |
res += f[i]; | res += f[i]; | ||
} | } |
Текущая версия на 11:43, 9 мая 2020
Дерево Фенвика — структура данных, умеющая решать задачу 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