矩形区域和

一句话理解

矩形区域和：用四个前缀和容斥。

为什么要学

子矩阵查询 O(1)。

讲解

sum(x1,y1,x2,y2)=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]。

画图记：大矩形减上面减左边，加回左上。

例子

右下前缀 - 上边 - 左边 + 左上。

常见错误

• 加回左上时符号写反。
• 坐标从 0 开始却减到 -1。