c++前缀和

1 2 3 4 5 6 7 8 9
这样一个序列的前缀和是
1 3 6 10 15 21 36 45
很简单，可以直接得出公式
d表示前缀和数组，a表示原数组

d[i] = d[i - 1] + a[i];

前缀和可以快速求出某以区间的值
如：就上面的那个数据，你想求a[2, 5]这个区间里的和，可以用前缀和d[5] - d[1]
证明
a[2, 5]这个区间里的和是a[2] + a[3] + a[4] + a[5]
而d[5] = a[1] + a[2] + a[3] + a[4] + a[5]
d[1] = a[1];
d[5] - d[1] = a[2] + a[3] + a[4] + a[5]
完整代码：

#includeusing namespace std;const int N = 1e5 + 10;int a[N];int f[N];int main() {int n;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= n; i++) f[i] = f[i - 1] + a[i];for (int i = 1; i <= n; i++) cout << f[i] << ' ';cout << endl;retrun 0;}

还有升级版的——二维前缀和
有一个矩阵
1 2 3
4 5 6
7 8 9
前缀和为
1 3 6
5 12 21
12 27 45
从1,1到x，y的前缀和为

d[i][j] = d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1] + a[i][j];

求x，y到xx，yy的值为 (xx > x, yy > y)

d[xx][yy] - d[x - 1][yy] - d[xx][y - 1] + d[x - 1][y - 1]

证明：

求D的面积就是：（A + B + C + D） - （B + A） - （C + A） + A