Bài toán yêu cầu thực hiện các thao tác cộng giá trị lên một vùng hình chữ nhật trên ma trận và truy vấn tổng các phần tử trong một vùng hình chữ nhật khác. Để giải quyết hiệu quả, chúng ta có thể áp dụng cấu trúc dữ liệu cây chỉ số nhị phân (Fenwick Tree) hai chiều kết hợp với kỹ thuật mảng hiệu.

Trước hết, hãy nhắc lại cách xây dựng cây Fenwick một chiều cho bài toán cập nhật khoảng và truy vấn khoảng. Cây Fenwick truyền thống chỉ hỗ trợ truy vấn tổng tiền tố và cập nhật tại một điểm. Để mở rộng, ta sử dụng mảng hiệu d. Nếu cần cộng giá trị k vào đoạn [l, r], ta thực hiện: add(l, k) và add(r+1, -k). Khi đó, tổng tiền tố đến vị trí p chính là giá trị phần tử tại p. Để truy vấn tổng các phần tử từ 1 đến n, ta cần tính:

\[\sum_{i=1}^{n} \sum_{j=1}^{i} d_j\]

Mỗi phần tử d_i đóng góp vào kết quả với hệ số (n - i + 1). Do đó, tổng cần tìm là:

\[(n+1)\sum_{i=1}^{n} d_i - \sum_{i=1}^{n} d_i \times i\]

Như vậy, chỉ cần duy trì hai cây Fenwick: một lưu tổng d_i và một lưu tổng d_i * i.

Code minh họa cho một chiều:

void update(int p, int val) {
    for (int i = p; i <= n; i += i & -i) {
        bit1[i] += val;
        bit2[i] += p * val;
    }
}

int prefix_sum(int p) {
    int res = 0;
    for (int i = p; i > 0; i -= i & -i) {
        res += (p + 1) * bit1[i] - bit2[i];
    }
    return res;
}

Áp dụng tương tự cho ma trận hai chiều. Định nghĩa mảng hiệu d sao cho tổng tiền tố hai chiều của d đến ô (x, y) bằng giá trị của ô a[x][y]. Công thức mảng hiệu:

\[d_{i,j} = a_{i,j} - a_{i-1,j} - a_{i,j-1} + a_{i-1,j-1}\]

Khi cộng giá trị k vào vùng có góc trên trái (x1, y1) và góc dưới phải (x2, y2), ta thực hiện bốn thao tác trên mảng hiệu:

add(x1, y1, k);
add(x2+1, y2+1, k);
add(x1, y2+1, -k);
add(x2+1, y1, -k);

Truy vấn tổng vùng từ (1,1) đến (x,y) yêu cầu tính:

\[\sum_{i=1}^{x} \sum_{j=1}^{y} \sum_{u=1}^{i} \sum_{v=1}^{j} d_{u,v}\]

Mỗi phần tử d_i,j xuất hiện trong các tổng con của các ô thuộc vùng [i, x] × [j, y], tức là đóng góp (x-i+1)*(y-j+1) lần. Khai triển biểu thức, ta có:

\[(x*y + x + y + 1) \cdot S_0 - (y+1) \cdot S_1 - (x+1) \cdot S_2 + S_3\]

Trong đó:

• \(S_0 = \sum \sum d_{i,j}\)
• \(S_1 = \sum \sum d_{i,j} \cdot i\)
• \(S_2 = \sum \sum d_{i,j} \cdot j\)
• \(S_3 = \sum \sum d_{i,j} \cdot i \cdot j\)

Do đó, ta cần xây dựng bốn cây Fenwick 2D, mỗi cây lưu một trong các tổng trên.

Code mẫu cho bài toán 2D:

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

const int MAXN = 2050;
int bit[MAXN][MAXN][4];
int n, m;

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

void add(int x, int y, int val) {
    if (x < 1 || x > n || y < 1 || y > m) return;
    int a = val * x, b = val * y, c = val * x * y;
    for (int i = x; i <= n; i += lowbit(i))
        for (int j = y; j <= m; j += lowbit(j)) {
            bit[i][j][0] += val;
            bit[i][j][1] += a;
            bit[i][j][2] += b;
            bit[i][j][3] += c;
        }
}

int query(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m) return 0;
    int s0 = 0, s1 = 0, s2 = 0, s3 = 0;
    for (int i = x; i > 0; i -= lowbit(i))
        for (int j = y; j > 0; j -= lowbit(j)) {
            s0 += bit[i][j][0];
            s1 += bit[i][j][1];
            s2 += bit[i][j][2];
            s3 += bit[i][j][3];
        }
    return s0 * (x * y + x + y + 1) - s1 * (y + 1) - s2 * (x + 1) + s3;
}

int main() {
    scanf("%*c %d %d", &n, &m);
    char op;
    int x1, y1, x2, y2, val;
    while (scanf(" %c %d %d %d %d", &op, &x1, &y1, &x2, &y2) != EOF) {
        if (op == 'L') {
            scanf("%d", &val);
            add(x1, y1, val);
            add(x2 + 1, y2 + 1, val);
            add(x1, y2 + 1, -val);
            add(x2 + 1, y1, -val);
        } else {
            int ans = query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
            printf("%d\n", ans);
        }
    }
    return 0;
}