前缀和

思路

为了计算更加快速，如果遇到繁琐，冗余的计算 例如：求 1 加到 n ，2 加到 n 3 加到 n 一直到 n 加到 n

另外，前缀和适用于矩阵求和 可以简单画图推导一下公式

前缀和 2024-03-27 22.46.12.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1]

Link to original

实现

//一般留下第一个为0
for(int i = 1; i <= n; i ++)
{
	cin >> a[i];
	a[i] += a[i-1];
}
 
for（int i = 1; i <= n; i ++)
	for(int j = 1; j <= n; j ++)
	{
		cin >> s[i][j];
		s[i][j] += s[i-1][j] + s[j-1][i] - s[i-1][j-1];
	}