前言

在P6180 【[USACO15DEC]Breed Counting S】这篇文章中，我介绍并使用了前缀和的方法来通过该题，这次来讲前缀和的扩展——二维前缀和。

什么是二维前缀和

首先，并不是针对二维数组中的每一横行作前缀和。

定义

这次，我们的前缀和数组 $b$ 的定义如下

$$b_{x,y}=\sum_{i=1}^x\sum_{j=1}^ya_{i,j}$$

如果您看不懂或者懒得看这个式子，不妨看看另一个形象一点的介绍

我们认为 $b{x,y}$ 就是 $a{x,y}$ ​左上方矩形的所有数之和。

我用 Excel 画了这么一张图，其中黄色为原数组 $a$ 黑色为前缀和数组 $b$ 红色部分为二者中相等的部分，也就是说 $b$ 的红色部分代表的是 $a$ 红色部分的和

计算方法

怎么得到 $b$ 数组呢？

如果我们要得到下图中被框起来的 $b$ 数组

可以如下图一样操作

不难发现，也就是加上 $b$ 中上方和左边的数（红色标识），去掉重复的部分（左上方橙色标识），加上原本没有的数（绿色标识）

给出公式

$$b_{x,y}=b_{x-1,y}+b_{x,y-1}-b_{x-1,y-1}+a_{x,y}$$

如何使用

要知道 $(x1,y1)-(x2,y2)$ 矩阵的值，一样可以由上述思想推出。

以求 $(2,2)-(3,3)$ 为例

经过观察可得答案就是 $b_{x2,y2}-b_{x1-1,y2}-b_{x2,y1-1}+b_{x1-1,y1-1}$

例题

先gugugu了。