Hướng dẫn giải của Truy vấn tổng trong khoảng trên 1 dãy số
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhập
Tác giả: Hiếu Nguyễn
, ,
Editorial for rqsum: Truy vấn tổng trong khoảng trên 1 dãy số
Hiểu bài toán
Bài toán yêu cầu xử lý một dãy số A gồm N phần tử và Q truy vấn. Có hai loại truy vấn: (1) tăng tất cả các phần tử trong đoạn [l, r] thêm x đơn vị, và (2) tính tổng các phần tử trong đoạn [l, r]. Với N, Q lên tới 10^5, các thao tác cập nhật và truy vấn tổng phải được thực hiện hiệu quả.
Các cách tiếp cận
Cách Brute Force (Naive)
#include <stdio.h>
int main() {
int N, Q;
scanf("%d %d", &N, &Q);
long long A[N + 1];
for (int i = 1; i <= N; i++) {
scanf("%lld", &A[i]);
}
while (Q--) {
int type;
scanf("%d", &type);
if (type == 1) {
int l, r, x;
scanf("%d %d %d", &l, &r, &x);
for (int k = l; k <= r; k++) {
A[k] += x;
}
} else {
int l, r;
scanf("%d %d", &l, &r);
long long sum = 0;
for (int k = l; k <= r; k++) {
sum += A[k];
}
printf("%lld\n", sum);
}
}
return 0;
}
- Time Complexity: O(Q * N)
- Space Complexity: O(N)
Phương pháp này sử dụng mảng thường để lưu trữ. Với mỗi truy vấn cập nhật (loại 1), nó duyệt qua từng phần tử trong đoạn [l, r] để cộng thêm x. Với mỗi truy vấn tổng (loại 2), nó duyệt qua đoạn [l, r] để tính tổng. Do Q và N đều lên tới 10^5, tổng số phép toán có thể lên tới 10^10, dẫn đến Time Limit Exceeded (TLE).
Cách Fenwick Tree (Binary Indexed Tree)
#include <stdio.h>
#include <string.h>
#define MAXN 100005
long long bit1[MAXN], bit2[MAXN];
int n;
void update(long long bit[], int idx, long long val) {
for (; idx <= n; idx += idx & -idx)
bit[idx] += val;
}
long long query(long long bit[], int idx) {
long long sum = 0;
for (; idx > 0; idx -= idx & -idx)
sum += bit[idx];
return sum;
}
void range_update(int l, int r, int x) {
update(bit1, l, x);
update(bit1, r + 1, -x);
update(bit2, l, 1LL * x * (l - 1));
update(bit2, r + 1, -1LL * x * r);
}
long long prefix_sum(int idx) {
return query(bit1, idx) * idx - query(bit2, idx);
}
int main() {
int q;
scanf("%d %d", &n, &q);
long long val;
for (int i = 1; i <= n; i++) {
scanf("%lld", &val);
range_update(i, i, val);
}
while (q--) {
int type, l, r;
scanf("%d", &type);
if (type == 1) {
int x;
scanf("%d %d %d", &l, &r, &x);
range_update(l, r, x);
} else {
scanf("%d %d", &l, &r);
printf("%lld\n", prefix_sum(r) - prefix_sum(l - 1));
}
}
return 0;
}
- Time Complexity: O(Q log N)
- Space Complexity: O(N)
Sử dụng 2 cây Fenwick (BIT) để xử lý Range Update và Range Query (RU-RQ). BIT1 lưu chênh lệch giá trị (difference array) để hỗ trợ cập nhật đoạn, BIT2 lưu trữ thông tin bổ sung để tính tổng tiền tố chính xác. Cập nhật đoạn [l, r] thêm x được thực hiện bằng 4 thao tác cập nhật đơn lẻ trên BIT. Truy vấn tổng đoạn [l, r] tính tổng tiền tố từ 1 đến r trừ đi tổng tiền tố từ 1 đến l-1. Đây là giải pháp tối ưu với độ phức tạp logarithmic.
Cách Segment Tree with Lazy Propagation
#include <stdio.h>
#include <string.h>
#define MAXN 100005
long long tree[4 * MAXN];
long long lazy[4 * MAXN];
long long A[MAXN];
int n;
void push(int node, int start, int end) {
if (lazy[node] != 0) {
tree[node] += (long long)(end - start + 1) * lazy[node];
if (start != end) {
lazy[node * 2] += lazy[node];
lazy[node * 2 + 1] += lazy[node];
}
lazy[node] = 0;
}
}
void build(int node, int start, int end) {
if (start == end) {
tree[node] = A[start];
} else {
int mid = (start + end) / 2;
build(node * 2, start, mid);
build(node * 2 + 1, mid + 1, end);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
}
void update(int node, int start, int end, int l, int r, int val) {
push(node, start, end);
if (start > r || end < l) return;
if (l <= start && end <= r) {
lazy[node] += val;
push(node, start, end);
return;
}
int mid = (start + end) / 2;
update(node * 2, start, mid, l, r, val);
update(node * 2 + 1, mid + 1, end, l, r, val);
tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
long long query(int node, int start, int end, int l, int r) {
push(node, start, end);
if (start > r || end < l) return 0;
if (l <= start && end <= r) return tree[node];
int mid = (start + end) / 2;
return query(node * 2, start, mid, l, r) + query(node * 2 + 1, mid + 1, end, l, r);
}
int main() {
int q;
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%lld", &A[i]);
build(1, 1, n);
while (q--) {
int type, l, r;
scanf("%d", &type);
if (type == 1) {
int x;
scanf("%d %d %d", &l, &r, &x);
update(1, 1, n, l, r, x);
} else {
scanf("%d %d", &l, &r);
printf("%lld\n", query(1, 1, n, l, r));
}
}
return 0;
}
- Time Complexity: O(Q log N)
- Space Complexity: O(N)
Sử dụng Segment Tree kết hợp với cơ chế Lazy Propagation (tạm dịch: đánh dấu trễ). Lazy Propagation cho phép trì hoãn các cập nhật đối với các nút con cho đến khi cần thiết. Điều này đảm bảo mỗi truy vấn cập nhật và truy vấn tổng chỉ tốn O(log N) thời gian. Cây Segment Tree lưu trữ tổng của các đoạn con, trong khi mảng 'lazy' lưu các giá trị cần cộng thêm chưa được đẩy xuống.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(Q * N) | O(N) | Brute Force (Naive) |
| 2 | O(Q log N) | O(N) | Fenwick Tree (Binary Indexed Tree) |
| 3 | O(Q log N) | O(N) | Segment Tree with Lazy Propagation |
Bài học kinh nghiệm
- Bài toán yêu cầu xử lý động 2 thao tác trên mảng: cập nhật đoạn và truy vấn tổng. Cấu trúc dữ liệu cây phân đoạn (Segment Tree) hoặc cây Fenwick (BIT) là phù hợp nhất.
- Giải pháp Brute Force chỉ hiệu quả khi N và Q nhỏ (< 10^4). Với约束 10^5, cần thuật toán O(log N) cho mỗi truy vấn.
- RU-RQ (Range Update Range Query) bằng BIT là cách tiếp cận tiết kiệm bộ nhớ và code ngắn gọn nhất cho bài toán này.
Lỗi thường gặp
- Lỗi tràn số nguyên (Integer Overflow): Tổng các phần tử có thể lên tới 10^10 hoặc hơn, bắt buộc phải dùng kiểu dữ liệu 64-bit (long long trong C/C++).
- Quên cơ chế Lazy Propagation khi dùng Segment Tree: Nếu không dùng lazy, mỗi cập nhật đoạn sẽ tốn O(N) thời gian, dẫn đến TLE.
- Lỗi chỉ số mảng (Off-by-one error): Phải thống nhất chỉ số mảng bắt đầu từ 0 hay 1 để tránh sai lệch khi tính toán.
Bình luận