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

• • Mảng cộng dồn (Prefix Sum) trên mảng 2 chiều trong C++ dùng để tính tổng các ô từ i,j tới x,y trong mảng a cho trước.
  • Ví dụ : ta có mảng 2 chiều gồm m dòng và n cột như sau:
  • Để tính tổng tính tổng các ô từ i, j tới x, y cụ thể từ ô [0][0] đến ô [2][2] bằng cách sử dụng mảng cộng dồn của f[2][2] và thực hiện như sau:
  • Nhắc lại kiến thức, cũng giống như mảng cộng dồn trên mảng 1 chiều để tính f[0][1] trên mảng 2 chiều ta cũng thực hiện như sau:
  • f[2][2] =f[2][1]+f[1][2]-f[1][1]+a[2][2]. Thuật toán ở đây ta trừ đi f[1][1] do trong quá trình cộng ta lặp lại 2 lần.
  • Từ 2 ví dụ trên ta suy ra được công thức tổng quát để tính tổng từ ô [0][0] đến ô [x][y] là: f[x][y]= a[x][y] + f[x][y-1] + f[x-1][y] – f[x-1][y-1]
  • Tiếp theo ta sẽ xây dựng công thức để tính tổng từ ô [i][j] đến ô [x][y] bất kì:
  • Ví dụ: tính tổng từ ô [2][2] đến ô [4][3]
  • Ta xây dựng công thức dựa vào bảng sau:
  • Công thức tổng quát để tính tổng S [i,j -> x,y]

S=f[x][y] – f[x][j-1]-f[i-1][y]+f[i-1][j-1]

• • Code C++:
  • Input :

 
#include <bits/stdc++.h>
using namespace std;
int m,n;
int a[1005][1005], f[1005][1005];
int main()
{
	freopen("input.inp","r",stdin); 
	freopen("output.out","w",stdout); 
	cin>>m>>n;
	for (int i = 0; i<m; i++)
		for (int j=0; j<n; j++)
			cin >> a[i][j];
			
	for (int i = 0; i<m; i++)
		for (int j=0; j<n; j++)
		f[i][j]= a[i][j] + f[i-1][j] + f[i][j-1] - f[i-1][j-1];
		cout << f[4][3] - f[4][1] - f[1][3] + f[1][1] << endl;
		cout << f[2][2];
	return 0;
}

• Kết quả: