前缀和与差分

介绍

一组对偶运算

graph TD
A([原数组])
B([前缀和数组])
C([差分数组])
A --前缀和--> B
A --差分--> C
B --差分--> A
C --前缀和--> A

作用

运算	查询	更新	功能
前缀和	$O(1)$区间查询	$O(n)$单点更新	快速求区间聚合值
差分	$O(n)$单点查询	$O(1)$区间更新	快速区间更新

前缀和

一维前缀和

递推公式

$sum_i = sum_{i-1} + a_i$

区间和

$sum_{(l,r)} = sum_r - sum_{l-1}$

二维前缀和

递推公式

$sum_{i,j} = sum_{i-1,j} + sum_{i,j-1} - sum_{i-1,j-1} + a_{i,j}$

区间和

$sum_{(x_1,y_1),(x_2,y_2)} = sum_{x_2,y_2} - sum_{x_1-1,y_2} - sum_{x_2,y_1-1} + sum_{x_1-1,y_1-1}$

差分

一维差分

递推公式

$d_i = a_i - a_{i-1}$

区间更新

$a_{(l,r)} + k$ $d_l + k,\\ d_{r+1} - k$

二维差分

递推公式

$d_{i,j} = (a_{i,j} - a_{i-1,j}) - (a_{i,j-1} - a_{i-1,j-1})$

区间更新

$a_{(x_1,y_1),(x_2,y_2)} + x$ $d_{x_1,y_1} + x,\\ d_{x_1,y_2+1} - x,\\ d_{x_2+1,y_1} - x,\\ d_{x_2+1,y_2+1} + x$