目录

复习：

二维前缀和数组：

引入：

边界元素的处理：

内部元素处理：

计算某个区域和：

 完整代码参考： 

优化：

---

复习：

在学习二维前缀和之前，我们先来复习一下一维前缀和：

给定一个数组

int arr[5]={1,2,3,4,5};

要求这个数组的前缀和，需要再创建一个数组sum[5]={0};当i=0时

sum[i]=arr[i];

 否则

sum[i]=sum[i-1]+arr[i];

这样arr的前缀和数组sum就求出来了，如果现在想要知道arr[i]到arr[j]的和，就可以用公式

sum[j]-sum[i-1];

来得到：

---

二维前缀和数组：

---

引入：

顾名思义，是二维数组中一个矩阵的前缀和，给定一个二维数组

int arr[4][4]={ 1, 2, 3, 4,
                5, 6, 7, 8,
                9,10,11,12,
                3,14,15,16};

想要求arr[0][0]到arr[2][2]的和，是多少呢？

很明显是1+2+3+5+6+7+9+10+11=54

但显然这种算法太慢，所以就有了二维前缀和。

和一维前缀和一样，我们需要先创建一个二维前缀和数组，在一维前缀和数组中每个元素是arr[0]到arr[i]的和，那么在二维前缀和数组中每个元素就是arr[0][0]到arr[i][j]的和，比如sum[2][2]的值就应该是54。

---

边界元素的处理：

在一维前缀和数组中，

sum[0]=arr[0];

这是一维的边界处理，二维前缀和数组的边界处理也类似，

对于i和j都为0的情况，sum[0][0]就等于arr[0][0]，如图：

对于i为0的情况，可以把sum[0]看作一个一维数组，即求sum[0]的一维前缀和

也就是上面提到过的公式：

sum[0][j]=sum[0][j-1]+arr[0][j];

对于j为0的情况，可以把竖着的sum[i][0]看做一个一维数组，即求sum[i][0]的一维前缀和

也就是上面提到过的公式：

sum[i][0]=sum[i-1][0]+arr[i][0];

内部元素处理：

在sum数组中，每个元素都是arr[0][0]到arr[i][j]的和，例如sum[1][1]，就是arr[0][0]到arr[1][1]的和，

可以写成如图这种形式：

也就是sum[1][0]+sum[0][1]-sum[0][0]+arr[1][1]：

即左边矩阵的和+上面矩阵的和-重复的矩阵的和

那么如果是求sum[2][2]，也就是

即

sum[1][2]+sum[2][1]-sum[1][1]+arr[2][2]

写成公式也就是

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];

最终结果为

代码实现：

int i,j;
    //计算二维前缀和数组
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
            if(i==0 && j==0)
                sum[i][j]=arr[i][j];
            else if(i==0)
                sum[0][j]=sum[0][j-1]+arr[0][j];
            else if(j==0)
                sum[i][0]=sum[i-1][0]+arr[i][0];
            else
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];

计算某个区域和：

区域和即arr[x][y]到arr[i][j]这个矩阵的值，例如arr[1][2]到arr[3][3]的和，也就是红色区域的和

拿出我们上面算好的二维前缀和数组，这就可以表示为

即arr[0][0]到arr[3][3]的和减去红色矩阵左边的矩阵，减去红色矩阵上面的矩阵，再加上重复减去的部分，也就是

即136-60-10+3=69

代码实现：

int x1,y1,x2,y2;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    if(x1==0 && y1==0)
        printf("%d\n",sum[x2][y2]);
    else if(x1==0)
        printf("%d\n",sum[x2][y2]-sum[x2][y1-1]);
    else if(y1==0)
        printf("%d\n",sum[x2][y2]-sum[x1-1][y2]);
    else
        printf("%d\n",sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]);

---

 完整代码参考： 

#include <stdio.h>
int arr[4][4]={ 1, 2, 3, 4,          
                5, 6, 7, 8,            
                9,10,11,12,
               13,14,15,16};            
int sum[4][4]={0};
void get_sum()//计算二维前缀和数组
{
    int i,j;
    //计算二维前缀和数组
    for(i=0;i<4;i++)
        for(j=0;j<4;j++)
            if(i==0 && j==0)
                sum[i][j]=arr[i][j];
            else if(i==0)
                sum[0][j]=sum[0][j-1]+arr[0][j];
            else if(j==0)
                sum[i][0]=sum[i-1][0]+arr[i][0];
            else
                sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];
}

void print_sum()//计算某个区域和   (x1,y1)到(x2,y2)的和
{
    int x1,y1,x2,y2;
    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
    if(x1==0 && y1==0)
        printf("%d\n",sum[x2][y2]);
    else if(x1==0)
        printf("%d\n",sum[x2][y2]-sum[x2][y1-1]);
    else if(y1==0)
        printf("%d\n",sum[x2][y2]-sum[x1-1][y2]);
    else
        printf("%d\n",sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1]);
}
int main()
{
    get_sum();//计算二维前缀和数组
    print_sum();//输出二维前缀和数组
    //如果输入的是1 1 2 2 则
    //sum[2][2]-sum[2][0]-sum[0][2]+sum[0][0]
    return 0;
}

---

优化：

上面的代码实现有点太复杂了，有没有什么办法能把那些繁琐的if else省掉呢？

如果我们给sum数组创建一个比原数组多一行一列的数组会怎么样？

在开辟时就比arr数组多一列，这样就不需要处理麻烦的边界元素了

只需要用

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i-1][j-1];

这一个公式就可以计算完毕，计算后的sum数组如下：

 

这样不会因为数组越界的原因而导致i和j为0的时候需要单独计算