前缀和

一维前缀和

令
$s [1] = a [1]$
$s [2] = a [1] + a [2]$
$s [3] = a [1] + a [2] + a [3]$

$\sum_{i=1}^na[i]$
那么

$s [i] = s [i - 1] + a [i]$

那么 $a [l]$ 到 $a [r]$ 的区间和

$\sum_{i=l}^ra[i] = s[r] - s[l-1]$

二维前缀和

令

$\sum_{x=1}^i\sum_{y=1}^ja[i][j]$
那么

$s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]\space\space\space\space\space\space(默认数组越界的s为0)$
那么 $x_1,y_1)到(x_2,y_2)的区间和$

$\sum_{x=x_1}^{x_2}\sum_{y=y1}^{y_2}a[i][j]=s[x_2][y_2]-s[x_1-1][y_2]-s[x_2][y_1-1]+s[x_1-1][y_1-1]$

差分

一维差分

令
$b [1] = a [1]$
$b [2] = a [2] - a [1]$
$b [3] = a [3] - a [2]$
$b [i] = a [i] - a [i - 1]$

那么

$a [i] = a [i - 1] + b [i]$

那么

$\sum_{i=1}^nb[i] = a[n]$

将 $a [l]$ 到 $a [r]$ 的区间加上 c
$a^{'}[l]\space\space\space\space\space\space\space=a[l] \space\space\space\space\space\space\space\space+\space c$
$a^{'}[l+1]=a[l+1]\space+\space c$
$a^{'}[l+2]=a[l+2]\space+\space c$
$\space...\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space...$
$a^{'}[r]\space\space\space\space\space\space=a[r]\space\space\space\space\space\space\space+\space c$

令
$b^{'}[l]\space\space\space\space\space\space\space=a^{'}[l] \space\space\space\space\space\space-\space a[l-1]$
$b^{'}[l+1]=a^{'}[l+1]-\space a^{'}[l]$
$a^{'}[l+2]=a^{'}[l+2] -\space a^{'}[l+1]$
$\space...\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space...$
$b^{'}[r]\space\space\space\space\space\space=a^{'}[r]\space\space\space\space\space\space\space-\space a^{'}[r-1]$
$b^{'}[r+1]=a[r+1]- a^{'}[r-1]$

那么
$b^{'}[l]\space\space\space\space\space\space\space=b[l]\space\space\space\space\space\space\space\space+d$
$b^{'}[l+1]=b[l+1]$
$b^{'}[l+2]=b[l+2]$
$\space...\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space...$
$b^{'}[r]\space\space\space\space\space\space=b[r]$
$b^{'}[r+1]=b[r+1]\space-d$

若将 $r$ 换成 $+\infty$ ，那么

$\Rightarrow\bigcap_{i=l}^{+\infty}(a[l]+=c)$

因此

$\bigcap_{i=l}^r(a[i]+=c)\Rightarrow \begin{cases} b[l]+=c\\ b[r+1]-=c \end{cases}$

二维差分

令

$\sum_{x=1}^i\sum_{y=1}^jb[i][j]=a[i][j]$

那么

$a [i] [j] = a [i - 1] [j] + a [i] [j - 1] - a [i - 1] [j - 1] + b [i] [j]$

那么

$b[i][j]+=c\Rightarrow \bigcap_{x=i}^{+\infty}\bigcap_{y=j}^{+\infty}(a[i][j]+=c)$

$a[i][j]+=c\Rightarrow \left\{ \begin{array}{c} b[i][j]+=c \\ b[i][j+1]-=c \\ b[i+1][j]-=c \\ b[i+1][j+1]+=c \end{array} \right.$

$\bigcap_{x=x_1}^{x_2}\bigcap_{y=y_1}^{y_2}(a[i][j]+=c)\Rightarrow \left\{ \begin{array}{c} b[x_1][y_1]+=c \\ b[x_1][y_2+1]-=c \\ b[x_2+1][y_1]-=c \\ b[x_2+1][y_2+1]+=c \end{array} \right.$

前缀和与差分的数学推导过程

前缀和

一维前缀和

二维前缀和

差分

一维差分

二维差分