Дерево Фенвика
Запрос суммы на отрезке, запрос добавления к отдельному элементу
Пусть имеется массив f[], каждый элемент которого хранит частичную сумму элементов массива a[], а именно а[i] = a[F(i)] + a[F(i) + 1] + ... + a[i - 1] + a[i], где F() — определённая функция.
Тогда сумма от 0 до r вычисляется следующим образом:
int query(int r) {
int res = 0;
for (int i = r; i >= 0; i = F(i) - 1)
res += f[i];
return res;
}
Пусть F(i) = i & (i + 1):
i = xx...x100...011...1 F(i) = xx...x100...000...0 F(i) - 1 = xx...x011...111...1
Можно видеть, что каждая операция i = (i & (i + 1)) - 1 будет обнулять в i один единичный разряд, что обеспечит логарифмическую сложность операции суммы.
Если некоторый элемент a[i] изменился, то должны таким же образом измениться все элементы f[j], где F(j) <= i <= j. После некоторых вычислений можно убедиться, что данным ограничениям удовлетворяет индекс i, а также все индексы, получаемые из i последовательностью изменений младшего нулевого разряда на единичный, то есть применений операции i |= (i + 1).
int query(int r) {
int res = 0;
for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
res += f[i];
return res;
}
void modify(int r, int val) {
for (int i = r; i < MAX_SIZE; i |= i + 1)
f[i] += val;
}
int sum(int l, int r) {
return query(r) - (l ? query(l - 1) : 0);
}
void add(int pos, int val) {
modify(pos, val);
}
Запрос отдельного элемента, запрос добавления на отрезке
Заменим массив a[] на массив deltaA[] по следующему правилу: deltaA[0] = a[0], deltaA[i] = a[i] - a[i - 1]. Построим дерево Фенвика по массиву deltaA[].
Тогда query(i) равно a[i], а вызов modify(pos, val) добавит val ко всем элементам a[], у которых i >= pos. Следовательно, чтобы увеличить элементы с индексами от l до r, нужно вызвать modify(l, val) и modify(r + 1, -val).
int get(int pos) {
return query(pos);
}
void add(int l, int r, int val) {
modify(l, val);
modify(r + 1, -val);
}
Запрос минимума на отрезке, запрос добавления к отдельному элементу
- Dima M., Ceterchi R. Efficient Range Minimum Queries using Binary Indexed Trees
- neerc.ifmo.ru/wiki — Встречное дерево Фенвика
Запрос суммы на отрезке, запрос добавления на отрезке
Метод P. Mishra
Пусть имеются деревья Фенвика T и Tx, и пусть (Tx.query(i) * i + T.query(i)) — сумма элементов массива a[] от a[0] до a[i]. Далее, пусть элементы массива a[] с индексами от l до r увеличились на величину val. Рассмотрим, как при этом изменится сумма элементов массива a[] от a[0] до a[i]:
- Если i < l, то сумма не изменилась, и значение (Tx.query(i) * i + T.query(i)) ей соответствует.
- Если l <= i <= r, то сумма увеличилась на (val * (i - l + 1)). Следовательно, к ячейкам Tx нужно добавить val, а к ячейкам T — (val * (-l + 1)).
- Если i > r, то сумма увеличилась на (val * (r - l + 1)). Следовательно, ячейки Tx изменять не нужно, а к ячейкам T нужно добавить (val * (r - l + 1)).
int prefixSum(int r) {
return Tx.query(r) * r + T.query(r);
}
int sum(int l, int r) {
return prefixSum(r) - (l ? prefixSum(l - 1) : 0);
}
void add(int l, int r, int val) {
Tx.modify(l, val);
Tx.modify(r + 1, -val); //Tx.modify(r + 1, 0 - val);
T.modify(l, val * (-l + 1));
T.modify(r + 1, val * r); //T.modify(r + 1, (val * (r - l + 1)) - (val * (-l + 1)));
}
- Mishra P. A New Algorithm for Updating and Querying Sub-arrays of Multidimensional Arrays
- petr-mitrichev.blogspot.ru — Fenwick tree range updates
- topcoder.com — How to modify BIT to update the ranges and query the ranges?
- topcoder.com — Range update in BIT
- kartikkukreja.wordpress.com — Range updates with BIT / Fenwick Tree
Данный метод может быть обобщён на большие размерности: Варианты дерева Фенвика
Метод М. Кормышова
Введём массив fAdd[], i-й элемент которого хранит значение, добавляемое ко всем элементам массива a[] на отрезке F(i)..i.
int query(int r) {
int res = 0;
for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
res += f[i] + fAdd[i] * (i - (i & (i + 1)) + 1);
for (int i = (r | (r + 1)); i < MAX_SIZE; i |= i + 1)
res += fAdd[i] * (r - (i & (i + 1)) + 1);
return res;
}
void modify(int r, int val) {
for (int i = r; i >= 0; i = (i & (i + 1)) - 1)
fAdd[i] += val;
for (int i = (r | (r + 1)); i < MAX_SIZE; i |= i + 1)
f[i] += val * (r - (i & (i + 1)) + 1);
}
int sum(int l, int r) {
return query(r) - (l ? query(l - 1) : 0);
}
void add(int l, int r, int val) {
modify(r, val);
if (l)
modify(l - 1, -val);
}
Ссылки
Теория:
Демонстрация:
Код:
Задачи: