二维前缀和

学习了前缀和，又想来搞二维前缀和了……

二维前缀和：建立一个矩阵，求矩阵内子矩阵内所有数的和。

下面给一个n×m的矩阵，给定左上角坐标（x₁,y₁）和右下角坐标，求右下角坐标（x₂,y₂），求子矩阵内元素的和。

让我们先初始化一个二维数组，并读入一些数据，下面是代码和输出：

    int a[11][11],s[11][11];
　　 memset(a,0,sizeof(a));
　　 memset(s,0,sizeof(s));
    for(int i=1;i<=10;i++){
        for(int j=1;j<=10;j++){
            a[i][j]=j*j;
            cout<<a[i][j]<<" ";
        }
        cout<<endl;
    }
    

输出：
1 4 9 16 25 36 49 64 81 100 
1 4 9 16 25 36 49 64 81 100 
1 4 9 16 25 36 49 64 81 100 
1 4 9 16 25 36 49 64 81 100 
1 4 9 16 25 36 49 64 81 100 
1 4 9 16 25 36 49 64 81 100 
1 4 9 16 25 36 49 64 81 100 
1 4 9 16 25 36 49 64 81 100 
1 4 9 16 25 36 49 64 81 100 
1 4 9 16 25 36 49 64 81 100 

 

那么现在来建立二维前缀和数组s，然后来求前缀和，但如果用暴力，那么时间复杂度较高，可以思考一下怎么样简化问题。

           　　　　

通过上面这张那个图片不难发现这个式子：

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

 

那么就可以开始写程序了：

    for(int i=1;i<=10;i++){
        for(int j=1;j<=10;j++){
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
            cout<<s[i][j]<<" ";
        }
        cout<<endl;
    }

输出：
1  5  14  30  55  91  140  204  285  385 
2  10 28  60  110 182 280  408  570  770 
3  15 42  90  165 273 420  612  855  1155 
4  20 56  120 220 364 560  816  1140 1540 
5  25 70  150 275 455 700  1020 1425 1925 
6  30 84  180 330 546 840  1224 1710 2310 
7  35 98  210 385 637 980  1428 1995 2695 
8  40 112 240 440 728 1120 1632 2280 3080 
9  45 126 270 495 819 1260 1836 2565 3465 
10 50 140 300 550 910 1400 2040 2850 3850