Префиксная сумма арқылы түсіндіру

Fenwick Tree префиксная сумма сияқты жұмыс істейді, бірақ одан ақылдырақ.

Обычная префиксная суммада біз мынаны сақтаймыз:

Сонда отрезоктағы сумманы тез табамыз:

Мысалы:

Fenwick осы проблеманы шешеді. Ол да суммаларды сақтайды, бірақ толық префикстерді емес, кішкентай отрезоктарды сақтайды.

tr деген не?

Fenwick ішінде бір массив болады:

int tr[N];

tr — Fenwick массиві. Әр tr[i] кішкентай бір отрезоктың суммасын сақтайды.

Ол отрезоктың размері lowbit арқылы табылады.

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

tr қалай құрылады?

Мына массив болсын:

Онда tr осындай суммаларды сақтайды:

Яғни tr original массивті сақтамайды. Ол әртүрлі кішкентай отрезоктардың суммасын сақтайды.

Сумма қалай табылады?

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-дан алады.

Сонда:

Біз барлық [1, 7] отрезогын тез жинадық:

Отрезоктағы сумма

[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 қосу деген сөз.

Енді позиция 3-ті сақтайтын барлық tr[i] жаңару керек.

Сол үшін осы ячейкаларға 5 қосамыз.

Егер мәнді ауыстыру керек болса

Егер a[pos]-ты жаңа мәнге ауыстыру керек болса, айырмашылықты табамыз.

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

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

Мысалы:

Fenwick мәнді напрямую ауыстырмайды. Ол айырмашылықты қосады.

Задача 1: 1D 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

1D 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;
}

2D Fenwick

2D Fenwick матрица үшін керек. Ол кәдімгі 2D prefix sum сияқты, бірақ обновление тез жасайды.

int tr[N][N];

Обычная 2D префиксная суммада:

2D 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] жаңарады.

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;
        }
    }
}

Егер клетканың мәнін ауыстыру керек болса, қайтадан diff табамыз.

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

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

Задача 2: 2D 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

2D 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;
}

Асимптотика