Hướng dẫn giải của Truy vấn tổng đoạn con
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 qsum: Truy vấn tổng đoạn con
Hiểu bài toán
Bài toán yêu cầu xử lý một dãy số và hai loại truy vấn: (1) Cập nhật giá trị tại một vị trí, (2) Tính tổng các phần tử trong một đoạn con. Với giới hạn n và Q lên tới 10^5, giải thuật cần xử lý nhanh chóng.
Các cách tiếp cận
Cách Brute Force
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
long long a[100005];
long long sumrange(int l,int r){
long long s = 0;
for (int i = l;i <= r;i++){
s += a[i];
}
return s;
}
int main(){
int n,q;
scanf("%d %d",&n,&q);
for (int i = 1;i <= n;i++){
scanf("%lld",&a[i]);
}
for (int i = 0;i < q;i++){
int type;
scanf("%d",&type);
if (type == 1){
int x;
long long y;
scanf("%d %lld",&x,&y);
a[x] += y;
} else {
int x;
int y;
scanf("%d %d",&x,&y);
printf("%lld ",sumrange(x,y));
}
}
return 0;
}
- Time Complexity: O(Q * n)
- Space Complexity: O(n)
Giải pháp này đi ngược với truy vấn loại 2: để tính tổng đoạn [u, v], nó duyệt qua từng phần tử trong khoảng đó và cộng dồn. Nếu có nhiều truy vấn loại 2 với đoạn dài, độ phức tạp sẽ rất cao (khoảng 10^10 phép tính), dẫn đến TLE (Time Limit Exceeded).
Cách Prefix Sum (Mảng cộng dồn)
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int main() {
int n, Q;
scanf("%d%d", &n, &Q);
long long a[n + 1]; // Mảng lưu giá trị ban đầu
long long prefix[n + 1]; // Mảng cộng dồn
a[0] = 0;
prefix[0] = 0;
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
prefix[i] = prefix[i-1] + a[i];
}
for (int j = 0; j < Q; j++) {
int type;
scanf("%d", &type);
if (type == 1) {
int pos;
long long x;
scanf("%d %lld", &pos, &x);
a[pos] += x;
// Cập nhật lại mảng cộng dồn từ vị trí thay đổi trở đi
for (int k = pos; k <= n; k++) {
prefix[k] += x;
}
} else if (type == 2) {
int u, v;
scanf("%d %d", &u, &v);
printf("%lld ", prefix[v] - prefix[u-1]);
}
}
return 0;
}
- Time Complexity: O(Q * n)
- Space Complexity: O(n)
Sử dụng mảng cộng dồn để tính tổng đoạn [u, v] nhanh O(1) bằng cách lấy prefix[v] - prefix[u-1]. Tuy nhiên, khi cập nhật giá trị (type 1), ta phải cập nhật lại toàn bộ các phần tử từ vị trí đó trở đi trong mảng prefix. Nếu cập nhật nhiều lần ở đầu mảng, độ phức tạp vẫn là O(Q * n) và dễ bị TLE.
Cách Fenwick Tree (Binary Indexed Tree)
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
long long bit[100005];
int n;
void update(int idx, int val) {
while (idx <= n) {
bit[idx] += val;
idx += idx & -idx;
}
}
long long query(int idx) {
long long sum = 0;
while (idx > 0) {
sum += bit[idx];
idx -= idx & -idx;
}
return sum;
}
int main() {
int Q;
scanf("%d %d", &n, &Q);
for (int i = 1; i <= n; i++) {
int val;
scanf("%d", &val);
update(i, val);
}
for (int i = 0; i < Q; i++) {
int type;
scanf("%d", &type);
if (type == 1) {
int idx, x;
scanf("%d %d", &idx, &x);
update(idx, x);
} else {
int u, v;
scanf("%d %d", &u, &v);
printf("%lld ", query(v) - query(u - 1));
}
}
return 0;
}
- Time Complexity: O(Q log n)
- Space Complexity: O(n)
Fenwick Tree (BIT) là cấu trúc dữ liệu tối ưu cho bài toán này. Nó cho phép cập nhật giá trị tại một vị trí và truy vấn tổng tiền tố trong thời gian O(log n). Cấu trúc cây bit dựa trên số nhị phân, cho phép thao tác rất nhanh. Đây là giải pháp tối ưu nhất trong các giải pháp được đệ trình.
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 |
| 2 | O(Q * n) | O(n) | Prefix Sum (Mảng cộng dồn) |
| 3 | O(Q log n) | O(n) | Fenwick Tree (Binary Indexed Tree) |
Bài học kinh nghiệm
- Bài toán yêu cầu xử lý Online (xử lý ngay khi có truy vấn) thay vì Offline.
- Giải thuật Brute Force chỉ hiệu quả khi Q nhỏ (<= 10^3). Với Q = 10^5, cần tối ưu hóa truy vấn xuống dưới O(log n) hoặc O(1).
- Cấu trúc dữ liệu cây (Fenwick Tree hoặc Segment Tree) là lựa chọn hàng đầu cho các bài toán cập nhật và truy vấn tổng/ max/ min trên đoạn.
Lỗi thường gặp
- Sử dụng biến kiểu int để lưu tổng, có thể bị tràn số (overflow) khi tổng vượt quá 2^31 - 1 (khoảng 2 tỷ). Nên dùng long long.
- Lỗi truy cập mảng: một số giải pháp dùng mảng 0-indexed nhưng input là 1-indexed (hoặc ngược lại) dẫn đến sai lệch vị trí 1 đơn vị.
- Quên xử lý truy vấn loại 1 đúng cách (ví dụ: không cập nhật giá trị vào mảng ban đầu nếu không dùng BIT).
Bình luận