Hướng giải của Cập Nhật Điểm Tổng Ma Trận Con
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.
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ả:
Hướng dẫn giải
Bài toán thực hiện cập nhật điểm và truy vấn tổng ma trận con trên lưới tọa độ \(N \times M\). Sử dụng 2D Segment Tree (Cây phân đoạn 2 chiều - cây lồng cây):
- Cấu trúc gồm một Segment Tree quản lý hàng.
- Tại mỗi node của Segment Tree hàng, ta lưu trữ một Segment Tree 1D quản lý cột.
- Khi thực hiện cập nhật điểm \((x, y) = val\), ta duyệt tìm trên chiều \(x\), tại mỗi node đi qua ta gọi cập nhật cột \(y\) tương ứng với độ phức tạp \(O(\log N \log M)\).
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
struct SegTree1D {
int m; vector<long long> tree;
SegTree1D() {}
SegTree1D(int size) { m = size; tree.assign(4 * m, 0); }
void update(int node, int start, int end, int y, long long val) {
if (start == end) { tree[node] = val; return; }
int mid = (start + end)/2;
if (y <= mid) update(2*node, start, mid, y, val);
else update(2*node+1, mid+1, end, y, val);
tree[node] = tree[2*node] + tree[2*node+1];
}
long long query(int node, int start, int end, int y1, int y2) {
if (y2 < start || end < y1) return 0;
if (y1 <= start && end <= y2) return tree[node];
int mid = (start + end)/2;
return query(2*node, start, mid, y1, y2) + query(2*node+1, mid+1, end, y1, y2);
}
};
struct SegTree2D {
int n, m; vector<SegTree1D> tree;
SegTree2D(int r, int c) {
n = r; m = c;
tree.assign(4 * n, SegTree1D(m));
}
void update_y(int node_x, int start_x, int end_x, int node_y, int start_y, int end_y, int y, long long val) {
if (start_y == end_y) {
if (start_x == end_x) {
tree[node_x].tree[node_y] = val;
} else {
tree[node_x].tree[node_y] = tree[2*node_x].tree[node_y] + tree[2*node_x+1].tree[node_y];
}
return;
}
int mid_y = (start_y + end_y)/2;
if (y <= mid_y) update_y(node_x, start_x, end_x, 2*node_y, start_y, mid_y, y, val);
else update_y(node_x, start_x, end_x, 2*node_y+1, mid_y+1, end_y, y, val);
tree[node_x].tree[node_y] = tree[node_x].tree[2*node_y] + tree[node_x].tree[2*node_y+1];
}
void update_x(int node_x, int start_x, int end_x, int x, int y, long long val) {
if (start_x != end_x) {
int mid_x = (start_x + end_x)/2;
if (x <= mid_x) update_x(2*node_x, start_x, mid_x, x, y, val);
else update_x(2*node_x+1, mid_x+1, end_x, x, y, val);
}
update_y(node_x, start_x, end_x, 1, 0, m-1, y, val);
}
long long query_y(int node_x, int node_y, int start_y, int end_y, int y1, int y2) {
if (y2 < start_y || end_y < y1) return 0;
if (y1 <= start_y && end_y <= y2) return tree[node_x].tree[node_y];
int mid_y = (start_y + end_y)/2;
return query_y(node_x, 2*node_y, start_y, mid_y, y1, y2) +
query_y(node_x, 2*node_y+1, mid_y+1, end_y, y1, y2);
}
long long query_x(int node_x, int start_x, int end_x, int x1, int x2, int y1, int y2) {
if (x2 < start_x || end_x < x1) return 0;
if (x1 <= start_x && end_x <= x2) return query_y(node_x, 1, 0, m-1, y1, y2);
int mid_x = (start_x + end_x)/2;
return query_x(2*node_x, start_x, mid_x, x1, x2, y1, y2) +
query_x(2*node_x+1, mid_x+1, end_x, x1, x2, y1, y2);
}
};
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
int n, m, q; if (!(cin >> n >> m >> q)) return 0;
SegTree2D st(n, m);
while (q--) {
int t; cin >> t;
if (t == 1) { int x, y; long long val; cin >> x >> y >> val; x--; y--; st.update_x(1, 0, n-1, x, y, val); }
else { int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2; x1--; y1--; x2--; y2--; cout << st.query_x(1, 0, n-1, x1, x2, y1, y2) << "\n"; }
}
}
Nhận xét