二维前缀和

一句话理解

二维前缀和：s[i][j] 表示左上角 (1,1) 到 (i,j) 的矩形和。

为什么要学

子矩阵求和。

讲解

s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]。容斥去掉重复加的部分。

例子

s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a[i][j];

上块 + 左块 - 左上交叉 + 当前格。

常见错误

• 减了两次或没减交叉。
• 边界 i=0 没清零。