前缀和

作用:求区间和

时间复杂度: $ O(n) $ 预处理, $ O(1) $ 查询.

预处理

假设原数组为$ a_1,a_2,a_3,… $

前缀和数组

$ sum_1=a_1 $

$ sum_2=a_1+a_2=sum_1+a_2 $

$ sum_3=a_1+a_2+a_3=sum_2+a_3 $

$ … $

查询

查询 $ [l,r] $ 区间内和：

$ a_l+a_{l+1}+a_{l+2}+…+a_{r-1}+a_{r} $

$ =(a_1+a_2+…+a_{r-1}+a_r)-(a_1+a_2+…+a_{l-2}+a_{l-1}) $

$ =sum_r-sum_{l-1} $

差分

作用:区间加

时间复杂度: $ O(n) $ 预处理, $ O(1) $ 修改.

本质上是前缀和的逆运算.

区间加

通过对前缀和的研究,可以发现,当 a[k] 增加了 x 时,

sum[k],sum[k+1], $ … $ 都增加了 $ x $ .

这样就实现了区间加.

对 $ [l,r] $ 区间进行加 $ x $ 操作时,只需将 sum[l] 增加 x , 并将 sum[r+1] 增加 -x 即可.

预处理

求差分数组 d (将原数组 a 当作前缀和).

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

移项,

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

这样就完成了转换.

应用

二维前缀和

预处理

基于容斥原理.

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j]

查询

求 $ (x_1,y_1) $ 到 $ (x_2,y_2) $ 的和.

$ \sum_{i=x_1}^{x_2} \sum_{j=y_1}^{y_2} a_{i,j} $ = sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1].