## 📝 Lời giải bài toán: Truy vấn tổng đoạn con
- (nếu bí quá thì mọi người có thể tham khảo nha)
### 💡 Ý tưởng chính
Để tính nhanh tổng các phần tử trong đoạn `[l, r]` nhiều lần, ta sử dụng kỹ thuật **Prefix Sum** (tổng tiền tố).
Thay vì tính lại tổng từng đoạn bằng cách duyệt từ `l` đến `r` (độ phức tạp `O(n*q)`), ta tính trước mảng tổng tiền tố `dp[i]` là tổng các phần tử từ `a[1]` đến `a[i]`, sau đó tính kết quả từng truy vấn trong `O(1)`.
---
#### Đọc dữ liệu và tạo mảng tổng tiền tố
- Tạo mảng `a[1..n]` để lưu dãy số đầu vào.
- Tạo mảng `dp[0..n]` sao cho:
- `dp[0] = 0`
- `dp[i] = dp[i-1] + a[i]` với `i` từ `1` đến `n`
#### Trả lời từng truy vấn
- Với mỗi truy vấn `(l, r)`, ta in ra `dp[r] - dp[l-1]`, là tổng các phần tử từ `a[l]` đến `a[r]`.
---
### Tại sao lại là `dp[r] - dp[l-1]`?
Vì:
- `dp[r]` chứa tổng `a[1] + a[2] + ... + a[r]`
- `dp[l-1]` chứa tổng `a[1] + ... + a[l-1]`
- Nên `dp[r] - dp[l-1] = a[l] + ... + a[r]`
---
### Độ phức tạp
- **Tiền xử lý**: `O(n)` để tạo mảng `dp`
- **Mỗi truy vấn**: `O(1)`
- **Tổng thời gian**: `O(n + q)` với `n` là số phần tử, `q` là số truy vấn
---
### Code
```cpp
#include <iostream>
#include <vector>
#include <fstream>
#define ll long long
using namespace std;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n, q;cin >> n >> q;
vector<ll> a(n + 1), dp(n + 1, 0);
for (ll i = 1; i <= n; i++) {
cin >> a[i];
dp[i] = dp[i - 1] + a[i];
}
while (q--) {
ll l, r;
cin >> l >> r;
cout << dp[r] - dp[l - 1] << "\n";
}
return 0;
}
```
còn đối với phương pháp thông thường như này:
```cpp
#include <iostream>
#include <vector>
#include <fstream>
#define ll long long
using namespace std;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n,q; cin >> n >> q;
vector<ll> a(n);
for(ll i = 1; i <= n; i++) {
cin >> a[i];
}
while(q--) {
ll l,r; cin >> l >> r;
ll sum = 0;
for(ll i = l; i <= r; i++) {
sum += a[i];
}
cout << sum << endl;
}
return 0;
}
```
thì không thể full test được đâu nhé!
supercoder
Created at
0 likes