前缀和（差分与原数组）

写这篇文章的目的是为了区分前缀和和差分转换为前缀和的过程。因为模板中只讲了差分的更新操作。

一维数组

已知原数组$$a\left [1\right],a\left [2\right],\cdots,a\left [n\right]$$
前缀和数组$$s\left [1\right],s\left [2\right],\cdots,s\left [n\right]$$
差分数组$$b\left [1\right],b\left [2\right],\cdots,b\left [n\right]$$

原数组求前缀和

//在原数组中求前缀和
//注意：a[0] = 0;
for (int i = 1;i <= n;i ++)
    a[i] += a[i - 1];
//另开一个数组存前缀和
for (int i = 1;i <= n;i ++)
    s[i] = s[i - 1] + a[i];

差分数组转化为前缀和

for (int i = 1;i <= n;i ++)
    b[i] += b[i - 1];

二维数组

已知原数组$$a\left [1,1\right],\cdots,a\left [n,m\right]$$
前缀和数组$$s\left [1,1\right],\cdots,s\left [n,m\right]$$
差分数组$$b\left [1,1\right],\cdots,b\left [n,m\right]$$

原数组求前缀和

for (int i = 1;i <= n;i ++)
    for (int j = 1;j <= m;j ++)
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

差分数组转化为前缀和

for (int i = 1;i <= n;i ++)
    for (int j = 1; j <= m;j ++)
        b[i][j] += b[i][j - 1] + b[i - 1][j] - b[i - 1][j - 1];