Объяснение через префиксные суммы

Дерево Фенвика работает почти как префиксная сумма, но умнее.

В обычной префиксной сумме мы храним:

Тогда сумму на отрезке можно найти быстро:

Например:

Дерево Фенвика решает эту проблему. Оно тоже хранит суммы, но не все префиксы полностью, а маленькие куски префиксов.

Что такое tr?

В Fenwick есть массив:

int tr[N];

tr — это массив дерева Фенвика. Каждая ячейка tr[i] хранит сумму маленького отрезка.

Размер этого отрезка зависит от функции lowbit.

int lowbit(int x) {
    return x & -x;
}

Как строится tr?

Пусть есть массив:

Тогда tr хранит такие суммы:

То есть tr не хранит сам массив. Он хранит суммы разных маленьких отрезков.

Как найти сумму?

Функция sum(pos) находит сумму от 1 до pos.

int sum(int pos) {
    int ans = 0;

    for (int i = pos; i > 0; i -= lowbit(i)) {
        ans += tr[i];
    }

    return ans;
}

Например, хотим найти:

Fenwick берет не каждый элемент отдельно, а готовые куски из tr.

Получается:

Мы быстро собрали весь отрезок:

Сумма на отрезке

Чтобы найти сумму на отрезке [l, r], используем две префиксные суммы:

int query(int l, int r) {
    return sum(r) - sum(l - 1);
}

Например:

Через Fenwick:

Как обновлять значение?

Fenwick умеет быстро прибавлять число к одному элементу.

void add(int pos, int x) {
    for (int i = pos; i <= n; i += lowbit(i)) {
        tr[i] += x;
    }
}

Например:

Это значит: к a[3] прибавить 5.

Теперь надо обновить все tr[i], которые содержат позицию 3.

Поэтому к этим ячейкам прибавляем 5.

Если нужно поменять значение

Если нужно не прибавить, а именно поменять a[pos] на новое значение, считаем разницу.

void change(int pos, int x) {
    int diff = x - a[pos];

    a[pos] = x;
    add(pos, diff);
}

Например:

То есть Fenwick не меняет значение напрямую. Он прибавляет разницу.

Задача 1: одномерный Fenwick

Дан массив из n чисел. Нужно обработать запросы:

Input

5 5
1 2 3 4 5
Q 1 5
Q 2 4
C 3 10
Q 1 5
Q 3 3

Output

15
9
22
10

Полная реализация одномерного Fenwick

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
int a[N];
int tr[N];

int lowbit(int x) {
    return x & -x;
}

void add(int pos, int x) {
    for (int i = pos; i <= n; i += lowbit(i)) {
        tr[i] += x;
    }
}

int sum(int pos) {
    int ans = 0;

    for (int i = pos; i > 0; i -= lowbit(i)) {
        ans += tr[i];
    }

    return ans;
}

int query(int l, int r) {
    return sum(r) - sum(l - 1);
}

void change(int pos, int x) {
    int diff = x - a[pos];

    a[pos] = x;
    add(pos, diff);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        add(i, a[i]);
    }

    while (q--) {
        char op;
        cin >> op;

        if (op == 'Q') {
            int l, r;
            cin >> l >> r;

            cout << query(l, r) << '\n';
        } else if (op == 'C') {
            int pos, x;
            cin >> pos >> x;

            change(pos, x);
        }
    }

    return 0;
}

Двумерный Fenwick

Двумерный Fenwick работает так же, как префиксная сумма в матрице. Только вместо одномерного массива используется таблица.

int tr[N][N];

В обычной двумерной префиксной сумме:

В двумерном Fenwick tr[x][y] тоже хранит сумму прямоугольника, но не всегда от (1, 1), а маленький кусок.

Как находится сумма в 2D?

Пусть есть матрица:

Найдем sum(3, 3). Это сумма прямоугольника от (1, 1) до (3, 3).

Fenwick берет несколько готовых прямоугольников:

Итого:

Сумма в прямоугольнике

Чтобы найти сумму в прямоугольнике от (x1, y1) до (x2, y2), используем четыре префиксные суммы.

int query(int x1, int y1, int x2, int y2) {
    return sum(x2, y2)
         - sum(x1 - 1, y2)
         - sum(x2, y1 - 1)
         + sum(x1 - 1, y1 - 1);
}

Как обновлять в 2D?

Если делаем:

Это значит: к клетке (3, 2) прибавить 5. Тогда обновятся все tr[i][j], прямоугольники которых содержат клетку (3, 2).

void add(int x, int y, int val) {
    for (int i = x; i <= n; i += lowbit(i)) {
        for (int j = y; j <= m; j += lowbit(j)) {
            tr[i][j] += val;
        }
    }
}

Если нужно поменять значение клетки, снова считаем разницу.

void change(int x, int y, int val) {
    int diff = val - a[x][y];

    a[x][y] = val;
    add(x, y, diff);
}

Задача 2: двумерный Fenwick

Дана матрица n × m. Нужно обрабатывать запросы:

Input

3 3 5
1 2 3
4 5 6
7 8 9
Q 1 1 3 3
Q 2 2 3 3
C 2 2 10
Q 1 1 3 3
Q 2 2 2 2

Output

45
28
50
10

Полная реализация двумерного Fenwick

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;

int n, m;
int a[N][N];
int tr[N][N];

int lowbit(int x) {
    return x & -x;
}

void add(int x, int y, int val) {
    for (int i = x; i <= n; i += lowbit(i)) {
        for (int j = y; j <= m; j += lowbit(j)) {
            tr[i][j] += val;
        }
    }
}

int sum(int x, int y) {
    int ans = 0;

    for (int i = x; i > 0; i -= lowbit(i)) {
        for (int j = y; j > 0; j -= lowbit(j)) {
            ans += tr[i][j];
        }
    }

    return ans;
}

int query(int x1, int y1, int x2, int y2) {
    return sum(x2, y2)
         - sum(x1 - 1, y2)
         - sum(x2, y1 - 1)
         + sum(x1 - 1, y1 - 1);
}

void change(int x, int y, int val) {
    int diff = val - a[x][y];

    a[x][y] = val;
    add(x, y, diff);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int q;
    cin >> n >> m >> q;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
            add(i, j, a[i][j]);
        }
    }

    while (q--) {
        char op;
        cin >> op;

        if (op == 'Q') {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;

            cout << query(x1, y1, x2, y2) << '\n';
        } else if (op == 'C') {
            int x, y, val;
            cin >> x >> y >> val;

            change(x, y, val);
        }
    }

    return 0;
}

Асимптотика