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. Đổi giá trị một ô từ $u$ sang $v$ là cộng chênh lệch $v - u$, nên cần giữ thêm mảng giá trị hiện tại.

Lưới ban đầu đã có số thì đừng gọi update cho từng ô. Chép lưới vào bit, rồi đẩy mỗi ô sang ô cha của nó theo cột, sau đó theo hàng, giống cách dựng Fenwick một chiều trong $O(n)$:

for (ll i = 1; i <= n; i++)
    for (ll j = 1; j <= n; j++) {
        ll k = j + (j & -j);
        if (k <= n) bit[i][k] += bit[i][j];
    }
for (ll i = 1; i <= n; i++) {
    ll k = i + (i & -i);
    if (k <= n)
        for (ll j = 1; j <= n; j++) bit[k][j] += bit[i][j];
}

Dựng tuyến tính nhanh gấp hơn 4 lần, vì mỗi ô chỉ được cộng hai lần thay cho cỡ $\log^2 n \approx 120$ lần.

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. Đúng hai hàm update, get ở trên. Tổng hình chữ nhật là 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.

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

Độ phức tạp: mỗi lệnh $O(\log^2 S) \approx 100$ bước.

Cộng hình, 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

Độ phức tạp: mỗi lệnh $O(\log^2 n)$, mỗi test thêm $O(n^2)$ để xóa.

Cộng hình, hỏi hình

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

Độ phức tạp: mỗi thao tác $O(\log^2 n)$.

Ba chiều

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

Độ phức tạp: mỗi thao tác $O(\log^3 N) \approx 343$ bước, câu hỏi gấp 8.