Mảng cộng dồn (Prefix Sum) trên mảng 1 chiều trong C++

• • 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:
    

    a[n]

    4

    -3

    5

    3

    7

    6

    9

    12

  • 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:
    

    4	-3
    f[0] = a[0]	a[1]

  • 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;
}