Hướng giải của Cập Nhật Điểm Tổng Lưới

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

Bài toán yêu cầu cập nhật giá trị tại một điểm (Point Update) và tính tổng các phần tử trong một vùng hình chữ nhật (Range Query). Đây là bài toán BIT 2D cơ bản nhất.

  1. Khởi tạo: Khởi tạo mảng bit kích thước \((N+1) \times (M+1)\) bằng \(0\).
  2. Cập nhật điểm: Với thao tác cộng thêm val vào ô (x, y):
    • Duyệt i từ x tăng dần i += i & -i.
    • Trong mỗi bước, duyệt j từ y tăng dần j += j & -j.
    • Cộng val vào bit[i][j].
  3. Truy vấn tổng: Để tính tổng hình chữ nhật từ \((x_1, y_1)\) đến \((x_2, y_2)\):
    • Áp dụng nguyên lý Bao hàm - Loại trừ: \[\text{sum} = Q(x_2, y_2) - Q(x_1-1, y_2) - Q(x_2, y_1-1) + Q(x_1-1, y_1-1)\]
    • Trong đó, hàm \(Q(x, y)\) tính tổng tiền tố từ ô \((1, 1)\) đến \((x, y)\) bằng cách giảm chỉ số i và j qua phép toán -= i & -i.

Mã nguồn C++ mẫu

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

int n, m, q;
vector<vector<long long>> bit;

void update(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;
        }
    }
}

long long query(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;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    if (!(cin >> n >> m >> q)) return 0;
    bit.assign(n + 1, vector<long long>(m + 1, 0));
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, y; long long val; cin >> x >> y >> val;
            update(x, y, val);
        } else {
            int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
            cout << query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1) << "\n";
        }
    }
}

Nhận xét

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