笔记:前缀和与差分

变量

假设 $a$ 的容量为 $n$

前缀和

一维前缀和

$$\text{prefix}[i] = a[1] + ... + a[i]$$

如果我想查询区间 $[x,y] \ (y>x)$ 的和

$$\text{sum}=\text{prefix}[y]-\text{prefix}[x-1]$$

没什么好说的,随机应变

二维前缀和

结论

$$\text{prefix}[i][j] = a[i][j] + \text{prefix}[i-1][j] + \text{prefix}[i][j-1] - \text{prefix}[i-1][j-1]$$

给定左上角 $(x_1, y_1)$ ,右下角 $(x_2, y_2)$ ,矩阵和为:

$$\text{sum} = \text{prefix}[x_2][y_2] - \text{prefix}[x_1-1][y_2] - \text{prefix}[x_2][y_1-1] + \text{prefix}[x_1-1][y_1-1]$$

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[1005][1005],prefix[1005][1005];
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            prefix[i][j]=a[i][j]+prefix[i-1][j]+prefix[i][j-1]-prefix[i-1][j-1];
    int x1,y1,x2,y2;
    cin>>x1>>y1>>x2>>y2;
    cout<<prefix[x2][y2]-prefix[x1-1][y2]-prefix[x2][y1-1]+prefix[x1-1][y1-1]<<endl;
}

理解直观表示

这里可以生成一个n*n的前缀和数组方便理解,把鼠标放在格子上有选中特效

简易理解: $\text{prefix}[i][j]表示了(0,0)至(i,j)范围矩阵中内除了自身所有节点的和$

这里有个工具可以渲染计算前缀和查询区间操作的推导示意图,黄色部分是蓝色部分和绿色部分的交叉部分

三维前缀和

评价:极其复杂,考到了就现推吧

递推式

$$\begin{aligned}
prefix[i][j][k]
&= a[i][j][k] \\
&\quad + prefix[i-1][j][k] + prefix[i][j-1][k] + prefix[i][j][k-1] \\
&\quad - prefix[i-1][j-1][k] - prefix[i-1][j][k-1] - prefix[i][j-1][k-1] \\
&\quad + prefix[i-1][j-1][k-1].
\end{aligned}$$

for(int i=1;i<=X;i++)
    for(int j=1;j<=Y;j++)
        for(int k=1;k<=Z;k++)
            p[i][j][k] = p[i-1][j][k] + p[i][j-1][k] + p[i][j][k-1]
                         - p[i-1][j-1][k] - p[i-1][j][k-1] - p[i][j-1][k-1]
                         + p[i-1][j-1][k-1] + a[i][j][k];

查询操作

要查询区间

$$[x_1..x_2]\times[y_1..y_2]\times[z_1..z_2]$$

之和,需对 prefix 做 8 次 “加减” 运算:

$$\begin{aligned}
\mathrm{sum}
&= prefix[x_2][y_2][z_2] \\
&\quad - prefix[x_1-1][y_2][z_2] - prefix[x_2][y_1-1][z_2] - prefix[x_2][y_2][z_1-1] \\
&\quad + prefix[x_1-1][y_1-1][z_2] + prefix[x_1-1][y_2][z_1-1] + prefix[x_2][y_1-1][z_1-1] \\
&\quad - prefix[x_1-1][y_1-1][z_1-1].
\end{aligned}$$

• 第 1 项：整个前缀和

• 第 2–4 项：减去在 x、y、z 维超出下界的三个半面

• 第 5–7 项：加回被多减的三个交叉边

• 第 8 项：减去多加的“角”

int sum = p[x2][y2][z2]
          - p[x1-1][y2][z2] - p[x2][y1-1][z2] - p[x2][y2][z1-1]
          + p[x1-1][y1-1][z2] + p[x1-1][y2][z1-1] + p[x2][y1-1][z1-1]
          - p[x1-1][y1-1][z1-1];

小结

复杂度分析

$$\begin{aligned}
\text{sum} =&\ \text{prefix}[x_2][y_2][z_2] \\
& -\ \text{prefix}[x_1-1][y_2][z_2] - \text{prefix}[x_2][y_1-1][z_2] - \text{prefix}[x_2][y_2][z_1-1] \\
& +\ \text{prefix}[x_1-1][y_1-1][z_2] + \text{prefix}[x_1-1][y_2][z_1-1] + \text{prefix}[x_2][y_1-1][z_1-1] \\
& -\ \text{prefix}[x_1-1][y_1-1][z_1-1]
\end{aligned}$$

应用(From GPT)

差分

一维差分

$$a[i] = \sum_{j=1}^{i} diff[j] \quad \text{或者等价地：} \quad diff[i] = a[i] - a[i-1]$$

构造

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

单次区间操作

假设操作区间 $[l,r]$

diff[l] += k;
diff[r+1] -= k;

还原

还原原数组

a[0] = 0;
for(int i=1;i<=n;i++)
    a[i]=a[i-1]+diff[i];

二维差分

$$\text{diff}[i][j] = a[i][j] - a[i-1][j] - a[i][j-1] + a[i-1][j-1]$$

构造

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

单次区间操作

diff[x1][y1]     += k;
diff[x2+1][y1]   -= k;
diff[x1][y2+1]   -= k;
diff[x2+1][y2+1] += k;

还原原数组

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

三维差分

$$\begin{aligned}
diff[i][j][k]
&= a[i][j][k] \\
&\quad - a[i-1][j][k] - a[i][j-1][k] - a[i][j][k-1] \\
&\quad + a[i-1][j-1][k] + a[i-1][j][k-1] + a[i][j-1][k-1] \\
&\quad - a[i-1][j-1][k-1].
\end{aligned}$$

$$\begin{cases}
diff[x_1][y_1][z_1] \mathrel{+}= k \\
diff[x_2+1][y_1][z_1] \mathrel{-}= k \\
diff[x_1][y_2+1][z_1] \mathrel{-}= k \\
diff[x_1][y_1][z_2+1] \mathrel{-}= k \\
diff[x_2+1][y_2+1][z_1] \mathrel{+}= k \\
diff[x_2+1][y_1][z_2+1] \mathrel{+}= k \\
diff[x_1][y_2+1][z_2+1] \mathrel{+}= k \\
diff[x_2+1][y_2+1][z_2+1] \mathrel{-}= k
\end{cases}$$

实际上就是前缀和的逆运算

for(int i=1;i<=X;i++)
  for(int j=1;j<=Y;j++)
    for(int k=1;k<=Z;k++)
      diff[i][j][k]=a[i][j][k]-a[i-1][j][k]-a[i][j-1][k]-a[i][j][k-1]
                    +a[i-1][j-1][k]+a[i-1][j][k-1]+a[i][j-1][k-1]-a[i-1][j-1][k-1];

单次区间操作

diff[x1][y1][z1]     += k;
diff[x2+1][y1][z1]   -= k;
diff[x1][y2+1][z1]   -= k;
diff[x1][y1][z2+1]   -= k;
diff[x2+1][y2+1][z1] += k;
diff[x2+1][y1][z2+1] += k;
diff[x1][y2+1][z2+1] += k;
diff[x2+1][y2+1][z2+1] -= k;

还原原数组

for(int i=1;i<=X;i++)
  for(int j=1;j<=Y;j++)
    for(int k=1;k<=Z;k++)
      a[i][j][k]=a[i-1][j][k]+a[i][j-1][k]+a[i][j][k-1]
                 -a[i-1][j-1][k]-a[i-1][j][k-1]-a[i][j-1][k-1]
                 +a[i-1][j-1][k-1]+diff[i][j][k];

小结

复杂度分析

应用(From GPT)

本文写作过于匆忙,以后有机会会维护