2D Fenwick Tree

Fenwick lồng nhau

bit[i][j] giữ tổng các ô $(x, y)$ với $x$ trong khối của $i$ và $y$ trong khối của $j$, khối theo nghĩa của Fenwick một chiều: từ $i - \mathrm{lowbit}(i) + 1$ tới $i$. Cộng vào ô $(x, y)$: nhảy $i = x, x + \mathrm{lowbit}(x), \dots$ và trong mỗi $i$ nhảy $j = y, y + \mathrm{lowbit}(y), \dots$. Tổng tiền tố $P(x, y)$ của hình chữ nhật $[1..x] \times [1..y]$ đi ngược lại. Tổng hình chữ nhật $[x_1..x_2] \times [y_1..y_2]$ theo bao hàm loại trừ:

void update(ll x, ll y, ll val) {
    for (ll i = x; i <= n; i += i & -i)
        for (ll j = y; j <= n; j += j & -j) bit[i][j] += val;
}

ll get(ll x, ll y) {
    ll res = 0;
    for (ll i = x; i > 0; i -= i & -i)
        for (ll j = y; j > 0; j -= j & -j) res += bit[i][j];
    return res;
}

Bộ nhớ $O(nm)$, nên chỉ hợp khi lưới vừa bộ nhớ (cỡ $2000 \times 2000$ số ll). Tọa độ bắt đầu từ 0 thì dịch thêm 1 trước khi vào cây.

Ví dụTổng Trên Lưới

Đề. Bảng $S \times S$ với $S \le 1024$, ban đầu toàn 0, tọa độ từ 0. Lệnh cộng $A$ vào một ô và lệnh hỏi tổng một hình chữ nhật; dừng ở lệnh 3.

Lời giải. Fenwick hai chiều: một cây Fenwick theo hàng, mỗi nút của nó lại là một cây Fenwick theo cột.

Bước 1: cập nhật. Vòng ngoài đi theo các nút của hàng $x$ (cộng bit thấp nhất), vòng trong đi theo các nút của cột $y$. Ô bit[i][j] giữ tổng một hình chữ nhật con, ghép từ hai đoạn Fenwick một chiều.

void update(ll x, ll y, ll val) {
    for (ll i = x; i <= n; i += i & -i)
        for (ll j = y; j <= n; j += j & -j) bit[i][j] += val;
}

Bước 2: tổng tiền tố. Tổng trên $[1..x] \times [1..y]$, cùng khuôn hai vòng nhưng trừ bit thấp nhất.

ll get(ll x, ll y) {
    ll res = 0;
    for (ll i = x; i > 0; i -= i & -i)
        for (ll j = y; j > 0; j -= j & -j) res += bit[i][j];
    return res;
}

Bước 3: tổng hình chữ nhật. Tiền tố góc phải trên trừ hai dải bên trái và bên dưới, cộng lại góc bị trừ hai lần. Tọa độ đề từ 0 mà Fenwick không có ô 0, nên mọi tọa độ cộng 1.

l++, b++, r++, tp++;
cout << get(r, tp) - get(l - 1, tp) - get(r, b - 1) + get(l - 1, b - 1) << '\n';

n được đọc ở lệnh 0, trước mọi lệnh khác.

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

const ll N = 1030;
ll n, bit[N][N];

void update(ll x, ll y, ll val) {
    for (ll i = x; i <= n; i += i & -i)
        for (ll j = y; j <= n; j += j & -j) bit[i][j] += val;
}

ll get(ll x, ll y) {
    ll res = 0;
    for (ll i = x; i > 0; i -= i & -i)
        for (ll j = y; j > 0; j -= j & -j) res += bit[i][j];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll t;
    while (cin >> t && t != 3) {
        if (t == 0) cin >> n;
        else if (t == 1) {
            ll x, y, a;
            cin >> x >> y >> a;
            update(x + 1, y + 1, a);
        } else {
            ll l, b, r, tp;
            cin >> l >> b >> r >> tp;
            l++, b++, r++, tp++;
            cout << get(r, tp) - get(l - 1, tp) - get(r, b - 1) + get(l - 1, b - 1) << '\n';
        }
    }
}

ChạyInput0 4
1 0 0 5
1 2 3 7
2 0 0 2 3
1 0 0 -2
2 0 0 0 0
3

Output12
3

Mỗi lệnh $O(\log^2 S) \approx 100$ bước.

Ví dụRừng Động

Đề. Rừng $n \times n$ với $n \le 1000$, ô có cây hoặc trống. $q \le 2 \cdot 10^5$ thao tác: đảo trạng thái một ô, hoặc đếm cây trong một hình chữ nhật.

Lời giải. Fenwick hai chiều đếm cây, update và get giống hệt ví dụ trước.

Bước 1: dựng ban đầu. Mỗi ô có cây là một lần cộng 1; mảng a giữ trạng thái hiện tại của ô. Trường hợp xấu nhất $n^2 \log^2 n \approx 10^8$ phép nhẹ, vẫn kịp; nếu cần nhanh hơn thì dựng từ tổng tiền tố trong $O(n^2)$.

if (s[j - 1] == '*') {
    a[i][j] = 1;
    update(i, j, 1);
}

Bước 2: đảo ô. Ô đang có cây thì cộng $-1$, trống thì cộng $+1$, rồi đảo a. Đề cho tọa độ theo (hàng, cột) là y, x; giữ đúng thứ tự đó cho cả cập nhật lẫn câu hỏi.

update(y, x, a[y][x] ? -1 : 1);
a[y][x] ^= 1;

Bước 3: đếm cây. Bốn tổng tiền tố như ví dụ trước.

cout << get(y2, x2) - get(y1 - 1, x2) - get(y2, x1 - 1) + get(y1 - 1, x1 - 1) << '\n';

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

const ll N = 1005;
ll n, q, a[N][N], bit[N][N];

void update(ll x, ll y, ll val) {
    for (ll i = x; i <= n; i += i & -i)
        for (ll j = y; j <= n; j += j & -j) bit[i][j] += val;
}

ll get(ll x, ll y) {
    ll res = 0;
    for (ll i = x; i > 0; i -= i & -i)
        for (ll j = y; j > 0; j -= j & -j) res += bit[i][j];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (ll i = 1; i <= n; i++) {
        string s;
        cin >> s;
        for (ll j = 1; j <= n; j++)
            if (s[j - 1] == '*') {
                a[i][j] = 1;
                update(i, j, 1);
            }
    }
    while (q--) {
        ll t;
        cin >> t;
        if (t == 1) {
            ll y, x;
            cin >> y >> x;
            update(y, x, a[y][x] ? -1 : 1);
            a[y][x] ^= 1;
        } else {
            ll y1, x1, y2, x2;
            cin >> y1 >> x1 >> y2 >> x2;
            cout << get(y2, x2) - get(y1 - 1, x2) - get(y2, x1 - 1) + get(y1 - 1, x1 - 1) << '\n';
        }
    }
}

ChạyInput3 4
*..
.*.
..*
2 1 1 3 3
1 2 2
2 1 1 2 2
2 3 3 3 3

Output3
1
1

Mỗi thao tác $O(\log^2 n)$.

Cập nhật hình chữ nhật, hỏi một ô

Mảng hiệu một chiều cộng $v$ vào đoạn $[l, r]$ bằng $+v$ tại $l$ và $-v$ tại $r + 1$; giá trị một điểm là tổng tiền tố. Hai chiều làm tương tự với bốn góc: cộng $v$ vào hình chữ nhật $[x_1..x_2] \times [y_1..y_2]$ là $+v$ tại $(x_1, y_1)$, $-v$ tại $(x_1, y_2 + 1)$ và $(x_2 + 1, y_1)$, $+v$ tại $(x_2 + 1, y_2 + 1)$. Giá trị ô $(x, y)$ là tổng tiền tố $P(x, y)$ của mảng hiệu, đúng một câu hỏi Fenwick hai chiều. Với phép lật bit, cộng thay bằng XOR và mọi dấu trừ đều là XOR.

Ví dụLật Hình Chữ Nhật

Đề. Nhiều test; mỗi test ma trận nhị phân $n \times n$ toàn 0, $n \le 1000$. Lệnh C lật mọi bit trong một hình chữ nhật, lệnh Q in bit tại một ô. In một dòng trống giữa kết quả hai test.

Lời giải. Lật bit là XOR 1. Giữ mảng hiệu hai chiều trong một Fenwick XOR: giá trị một ô là XOR tiền tố của mảng hiệu.

Bước 1: Fenwick XOR. Như Fenwick cộng, mọi phép cộng thành XOR.

void update(ll x, ll y) {
    for (ll i = x; i <= n; i += i & -i)
        for (ll j = y; j <= n; j += j & -j) bit[i][j] ^= 1;
}

Bước 2: lật hình chữ nhật. XOR 1 tại bốn góc của mảng hiệu. Góc ở hàng hay cột $n + 1$ bị vòng lặp bỏ qua, không sao vì chúng chỉ ảnh hưởng các ô ngoài bảng.

update(x1, y1);
update(x1, y2 + 1);
update(x2 + 1, y1);
update(x2 + 1, y2 + 1);

Bước 3: nhiều test. Mỗi test xóa đúng $n \times n$ ô đã dùng, không cần xóa cả mảng. In dòng trống trước mọi test trừ test đầu, tức giữa hai test liền nhau.

for (ll i = 1; i <= n; i++)
    for (ll j = 1; j <= n; j++) bit[i][j] = 0;
if (tc > 1) cout << '\n';

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

const ll N = 1005;
ll n, bit[N][N];

void update(ll x, ll y) {
    for (ll i = x; i <= n; i += i & -i)
        for (ll j = y; j <= n; j += j & -j) bit[i][j] ^= 1;
}

ll get(ll x, ll y) {
    ll res = 0;
    for (ll i = x; i > 0; i -= i & -i)
        for (ll j = y; j > 0; j -= j & -j) res ^= bit[i][j];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll T;
    cin >> T;
    for (ll tc = 1; tc <= T; tc++) {
        ll q;
        cin >> n >> q;
        for (ll i = 1; i <= n; i++)
            for (ll j = 1; j <= n; j++) bit[i][j] = 0;
        if (tc > 1) cout << '\n';
        while (q--) {
            char op;
            cin >> op;
            if (op == 'C') {
                ll x1, y1, x2, y2;
                cin >> x1 >> y1 >> x2 >> y2;
                update(x1, y1);
                update(x1, y2 + 1);
                update(x2 + 1, y1);
                update(x2 + 1, y2 + 1);
            } else {
                ll x, y;
                cin >> x >> y;
                cout << get(x, y) << '\n';
            }
        }
    }
}

ChạyInput2
3 3
C 1 1 2 2
Q 1 1
Q 3 3
2 2
C 1 2 2 2
Q 2 2

Output1
0

1

Mỗi lệnh $O(\log^2 n)$, mỗi test thêm $O(n^2)$ để xóa.

Cập nhật và hỏi hình chữ nhật

Muốn cả cập nhật hình chữ nhật lẫn hỏi tổng hình chữ nhật, tổng tiền tố của mảng giá trị phải tính từ mảng hiệu $d$: $P(x, y) = \sum_{i \le x, j \le y} d_{ij} \cdot (x - i + 1)(y - j + 1)$. Khai triển tích ra bốn số hạng, mỗi số hạng là một Fenwick hai chiều riêng ($d$, $d \cdot i$, $d \cdot j$, $d \cdot ij$). Với XOR, tích $(x - i + 1)(y - j + 1)$ chỉ cần tính chẵn lẻ: $d_{ij}$ góp vào $P(x, y)$ khi và chỉ khi $x - i$ và $y - j$ đều chẵn, tức $i$ cùng tính chẵn lẻ với $x$ và $j$ cùng với $y$. Vậy giữ bốn cây theo $(i \bmod 2, j \bmod 2)$; cập nhật góc $(i, j)$ vào cây của nó, hỏi tiền tố $(x, y)$ chỉ đọc cây $(x \bmod 2, y \bmod 2)$.

Ví dụXOR Trên Ma Trận

Đề. Ma trận $n \times n$ với $n \le 1000$, ban đầu 0. $m \le 10^5$ thao tác: XOR $v < 2^{62}$ vào mọi ô một hình chữ nhật, hoặc in XOR mọi ô một hình chữ nhật.

Lời giải. Cập nhật hình chữ nhật là XOR $v$ tại bốn góc của mảng hiệu, câu hỏi hình chữ nhật là XOR bốn tiền tố như bao hàm loại trừ. Khó là phải lấy XOR tiền tố của XOR tiền tố. Góc $(i, j)$ của mảng hiệu góp vào XOR tiền tố tại $(x, y)$ đúng $(x - i + 1)(y - j + 1)$ lần, và lặp chẵn lần thì triệt tiêu. Vậy chỉ những góc có $i \equiv x$ và $j \equiv y \pmod 2$ còn lại: chia mảng hiệu thành bốn cây Fenwick theo tính chẵn lẻ của tọa độ.

Bước 1: chọn cây. bit[x & 1][y & 1] là cây của góc $(x, y)$. Cả cập nhật lẫn câu hỏi chọn cây theo chính tọa độ gốc $(x, y)$, không theo các nút $(i, j)$ đi qua.

void update(ll x, ll y, ll v) {
    for (ll i = x; i <= n; i += i & -i)
        for (ll j = y; j <= n; j += j & -j) bit[x & 1][y & 1][i][j] ^= v;
}

Bước 2: cập nhật và câu hỏi. Cập nhật XOR $v$ tại bốn góc; câu hỏi XOR bốn tiền tố, mọi dấu trừ thành XOR.

if (t == 1) cout << (get(x1, y1) ^ get(x0 - 1, y1) ^ get(x1, y0 - 1) ^ get(x0 - 1, y0 - 1)) << '\n';
else {
    ll v;
    cin >> v;
    update(x0, y0, v);
    update(x0, y1 + 1, v);
    update(x1 + 1, y0, v);
    update(x1 + 1, y1 + 1, v);
}

Giá trị dưới $2^{62}$ nên dùng long long; bốn cây $1005^2$ số khoảng 32 MB.

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

const ll N = 1005;
ll n, m, bit[2][2][N][N];

void update(ll x, ll y, ll v) {
    for (ll i = x; i <= n; i += i & -i)
        for (ll j = y; j <= n; j += j & -j) bit[x & 1][y & 1][i][j] ^= v;
}

ll get(ll x, ll y) {
    ll res = 0;
    for (ll i = x; i > 0; i -= i & -i)
        for (ll j = y; j > 0; j -= j & -j) res ^= bit[x & 1][y & 1][i][j];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    while (m--) {
        ll t, x0, y0, x1, y1;
        cin >> t >> x0 >> y0 >> x1 >> y1;
        if (t == 1) cout << (get(x1, y1) ^ get(x0 - 1, y1) ^ get(x1, y0 - 1) ^ get(x0 - 1, y0 - 1)) << '\n';
        else {
            ll v;
            cin >> v;
            update(x0, y0, v);
            update(x0, y1 + 1, v);
            update(x1 + 1, y0, v);
            update(x1 + 1, y1 + 1, v);
        }
    }
}

ChạyInput3 4
2 1 1 2 2 5
1 1 1 1 1
2 2 2 3 3 3
1 1 1 3 3

Output5
0

Mỗi thao tác $O(\log^2 n)$.

Thêm một chiều nữa

Fenwick lồng được bao nhiêu tầng cũng được: ba chiều là ba vòng lặp lồng nhau, mỗi thao tác $O(\log^3 n)$. Tổng một hộp theo bao hàm loại trừ cần tám tổng tiền tố, dấu là $(-1)$ mũ số tọa độ lấy cận dưới. Bộ nhớ $n^3$ nhanh chóng trở thành giới hạn: $128^3$ số ll là 16 MB, $256^3$ đã 128 MB.

Ví dụKhông Gian UFO

Đề. Khối $N \times N \times N$ với $N \le 128$, tọa độ từ 0. Tới $10^5$ lệnh: cộng vào một ô, hoặc hỏi tổng một hộp; dừng ở lệnh 3.

Lời giải. Fenwick ba chiều: thêm một vòng lặp lồng cho chiều thứ ba. Tổng một hộp ghép từ tám tiền tố theo bao hàm loại trừ.

Bước 1: cập nhật và tiền tố. Ba vòng lồng nhau, tọa độ đề cộng 1 trước khi đưa vào cây.

void update(ll x, ll y, ll z, ll val) {
    for (ll i = x; i <= n; i += i & -i)
        for (ll j = y; j <= n; j += j & -j)
            for (ll k = z; k <= n; k += k & -k) bit[i][j][k] += val;
}

Bước 2: tám góc. Mặt nạ s 3 bit chọn cho mỗi chiều cận trên hay cận dưới. Trên cây, tiền tố tới cận trên là $hi + 1$, còn tiền tố đứng ngay trước cận dưới là $lo$ (tọa độ $lo - 1$ của đề cộng 1). Mỗi bit bật đổi dấu một lần, đúng dấu của bao hàm loại trừ. Khi $lo = 0$ thì tiền tố tới 0 bằng 0, đúng như mong muốn.

for (ll s = 0; s < 8; s++) {
    ll c[3], sign = 1;
    for (ll d = 0; d < 3; d++) {
        if (s >> d & 1) {
            c[d] = lo[d];
            sign = -sign;
        } else c[d] = hi[d] + 1;
    }
    res += sign * get(c[0], c[1], c[2]);
}

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

const ll N = 130;
ll n, bit[N][N][N];

void update(ll x, ll y, ll z, ll val) {
    for (ll i = x; i <= n; i += i & -i)
        for (ll j = y; j <= n; j += j & -j)
            for (ll k = z; k <= n; k += k & -k) bit[i][j][k] += val;
}

ll get(ll x, ll y, ll z) {
    ll res = 0;
    for (ll i = x; i > 0; i -= i & -i)
        for (ll j = y; j > 0; j -= j & -j)
            for (ll k = z; k > 0; k -= k & -k) res += bit[i][j][k];
    return res;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    ll t;
    while (cin >> t && t != 3) {
        if (t == 1) {
            ll x, y, z, k;
            cin >> x >> y >> z >> k;
            update(x + 1, y + 1, z + 1, k);
        } else {
            ll lo[3], hi[3];
            cin >> lo[0] >> lo[1] >> lo[2] >> hi[0] >> hi[1] >> hi[2];
            ll res = 0;
            for (ll s = 0; s < 8; s++) {
                ll c[3], sign = 1;
                for (ll d = 0; d < 3; d++) {
                    if (s >> d & 1) {
                        c[d] = lo[d];
                        sign = -sign;
                    } else c[d] = hi[d] + 1;
                }
                res += sign * get(c[0], c[1], c[2]);
            }
            cout << res << '\n';
        }
    }
}

ChạyInput3
1 0 0 0 4
1 2 1 2 3
2 0 0 0 2 2 2
1 0 0 0 -1
2 0 0 0 0 0 0
3

Output7
3

Mỗi thao tác $O(\log^3 N) \approx 343$ bước, câu hỏi gấp 8.