-
- Mảng cộng dồn (Prefix Sum) trên mảng 1 chiều trong C++ dùng để tính tổng các phần tử từ vị trí đầu tiên của mảng đến vị trí bất kì trong mảng hoặc tính tổng trên đoạn nào đó của mảng 1 chiều.
- Ví dụ : prefix sum trên mảng 1 chiều a gồm các phần tử sau:
- Tạo mảng cộng dồn f[]:
a[i] |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
a[n] |
4 |
-3 |
5 |
3 |
7 |
6 |
9 |
12 |
prefix sum/f |
|
|
|
|
|
|
|
|
- Để tính tổng a[0] + a[1] ta thực hiện như sau:
- Dựa vào bảng trên ta có được kết quả : a[0] + a[1] = f[1]= f[0]+a[1]
- Để tính tổng a[0] + a[1] + a[2] + a[3] + a[4] :
4 |
-3 |
5 |
3 |
7 |
a[0] + a[1] + a[2] + a[3] = f[3] |
a[4] |
a[0] + a[1] + a[2] + a[3] + a[4] = f[3] + a[4] |
- Từ đó 2 ví dụ trên ta suy ra được công thức tổng quát cho mảng cộng dồn bắt đầu từ vị trí đầu tiên a[0] như sau: f[i]=f[i-1]+a[i]
- Tiếp theo ta sẽ xây dựng công thức cho mảng cộng dồn trên đoạn bất kì của mảng a[n]
- Tính tổng a[2]+a[3]+…+a[7]:

- Công thức tổng quát để tính tổng trên đoạn S[i…j] = f[j]-f[i-1]
- Code C++
#include <bits/stdc++.h>
using namespace std;
int n;
int a[1005], f[1005];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
freopen("input.inp","r",stdin);
freopen("output.out","w",stdout);
cin >> n;
for (int i=0; i< n; i++){
cin >> a[i];
}
for (int i=0; i<n; i++)
f[i] = f[i-1]+a[i];//s[0..i]
cout<<f[5]-f[1];//S[i...j] = f[j]-f[i-1]; s[2..5]
return 0;
}
Số lượt xem: 2,924