Hướng dẫn giải của [200 đề thầy Đức] Bài 181: Truy vấn tổng
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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.
Hướng dẫn giải
Cho dãy N số nguyên và Q truy vấn, mỗi truy vấn hỏi tổng các phần tử từ l đến r. Với N, Q ≤ 10^5, nếu tính từng truy vấn bằng cách cộng trực tiếp thì quá chậm.
Sub 1: Vét cạn — ~O(N·Q)~
Với mỗi truy vấn (l, r), cộng trực tiếp các phần tử A[l] … A[r]. Cách này đúng nhưng khi N và Q cùng lớn thì số phép cộng lên tới 10^10. Đạt 16/20 test, 4 test còn lại quá giờ.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
vector<long long> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
// Vét cạn: mỗi truy vấn cộng trực tiếp các phần tử trong đoạn [l, r]
while (q--) {
int l, r;
cin >> l >> r;
long long s = 0;
for (int i = l; i <= r; i++) s += a[i];
cout << s << "\n";
}
return 0;
}
Sub 2: Mảng cộng dồn (prefix sum) — ~O(N + Q)~
Tạo mảng pre với pre[i] = A[1] + … + A[i] trong một lần duyệt. Khi đó tổng đoạn [l, r] bằng pre[r] - pre[l-1], tức là mỗi truy vấn chỉ cần O(1).
Bẫy cần chú ý: tổng có thể lên tới 10^3 × 10^5 = 10^8 nên dùng long long cho an toàn; và pre[0] = 0 để truy vấn l = 1 vẫn đúng. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
// Mảng cộng dồn: pre[i] = A[1] + ... + A[i]
vector<long long> pre(n + 1, 0);
for (int i = 1; i <= n; i++) {
long long x;
cin >> x;
pre[i] = pre[i - 1] + x;
}
// Tổng đoạn [l, r] = pre[r] - pre[l-1], mỗi truy vấn O(1)
while (q--) {
int l, r;
cin >> l >> r;
cout << pre[r] - pre[l - 1] << "\n";
}
return 0;
}
Bình luận