Hướng giải của Cộng Đoạn Lưới Tính Tổng

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Đây là bài toán nâng cao: Cập nhật đoạn trên lưới 2D (Range Update 2D) và tính tổng trên đoạn lưới 2D (Range Query 2D). Để giải quyết trong thời gian \(O(\log N \log M)\), ta cần sử dụng 4 cây BIT 2D độc lập.

Theo công thức mảng hiệu 2D, tổng tiền tố từ \((1, 1)\) đến \((x, y)\) khi thực hiện cập nhật \(val\) tại vị trí \((u, v)\) có dạng: \[S(x, y) = \sum_{i=1}^x \sum_{j=1}^y A[i][j] = \sum_{i=1}^x \sum_{j=1}^y \sum_{u=1}^i \sum_{v=1}^j D[u][v]\]

Khai triển công thức này, ta được: \[S(x, y) = \sum_{u=1}^x \sum_{v=1}^y D[u][v] \cdot (x - u + 1) \cdot (y - v + 1)\] \[S(x, y) = (x+1)(y+1)\sum D[u][v] - (y+1)\sum (u-1)D[u][v] - (x+1)\sum (v-1)D[u][v] + \sum (u-1)(v-1)D[u][v]\]

Do đó, ta cần duy trì 4 cây BIT 2D để quản lý các giá trị:

  1. \(D[u][v]\)
  2. \(D[u][v] \cdot (u-1)\)
  3. \(D[u][v] \cdot (v-1)\)
  4. \(D[u][v] \cdot (u-1)(v-1)\)

Mã nguồn C++ mẫu

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

int n, m, q;
vector<vector<long long>> bit1, bit2, bit3, bit4;

void update(vector<vector<long long>>& bit, int x, int y, long long val) {
    for (int i = x; i <= n; i += i & -i) {
        for (int j = y; j <= m; j += j & -j) {
            bit[i][j] += val;
        }
    }
}

void update_point(int x, int y, long long val) {
    update(bit1, x, y, val);
    update(bit2, x, y, val * (x - 1));
    update(bit3, x, y, val * (y - 1));
    update(bit4, x, y, val * (x - 1) * (y - 1));
}

void range_update(int x1, int y1, int x2, int y2, long long val) {
    update_point(x1, y1, val);
    update_point(x1, y2 + 1, -val);
    update_point(x2 + 1, y1, -val);
    update_point(x2 + 1, y2 + 1, val);
}

long long query(const vector<vector<long long>>& bit, int x, int y) {
    long long s = 0;
    for (int i = x; i > 0; i -= i & -i) {
        for (int j = y; j > 0; j -= j & -j) {
            s += bit[i][j];
        }
    }
    return s;
}

long long prefix_query(int x, int y) {
    return query(bit1, x, y) * x * y 
         - query(bit2, x, y) * y 
         - query(bit3, x, y) * x 
         + query(bit4, x, y);
}

long long range_query(int x1, int y1, int x2, int y2) {
    return prefix_query(x2, y2) - prefix_query(x1 - 1, y2) 
         - prefix_query(x2, y1 - 1) + prefix_query(x1 - 1, y1 - 1);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    if (!(cin >> n >> m >> q)) return 0;
    bit1.assign(n + 2, vector<long long>(m + 2, 0));
    bit2.assign(n + 2, vector<long long>(m + 2, 0));
    bit3.assign(n + 2, vector<long long>(m + 2, 0));
    bit4.assign(n + 2, vector<long long>(m + 2, 0));
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x1, y1, x2, y2; long long val; cin >> x1 >> y1 >> x2 >> y2 >> val;
            range_update(x1, y1, x2, y2, val);
        } else {
            int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
            cout << range_query(x1, y1, x2, y2) << "\n";
        }
    }
}

Nhận xét

Không có ý kiến tại thời điểm này.