C++ 代码

/**二维数组的前缀和  那就是二维
 * 1.s[i][j]怎么计算
 * 2.(x1,y1),(x2,y2)这一子矩阵中所有数的和怎么计算
 * 1.s[i,j]=s[i-1,j]+s[i,j-1]-s[i-1,j-1].
 * 2.=s[x2,y2]-s[x1-1,y2]-s[x2,y1-1]+s[x1-1,y1-1]
 *这个题如果用1维的做会超时。c++一秒可以执行10^8次指令 这个题是是n*p  大概是2*10^8次方 。。。好吧 超时了
 * 这个题真的可以 卡时间 非常到位 俺点歌赞。
 * 二维的时间复杂度 就是p
 * 
*/


import java.util.*;
public class Main{
    public static void main(String [] args){
        Scanner sc=new Scanner(System.in);
        int N=1009;
        int M=1009;
        int n=sc.nextInt();
        int m=sc.nextInt();
        int q=sc.nextInt();
        int[][] a=new int[N][M];
        int[][] s=new int[N][M];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++){
                a[i][j]=sc.nextInt();
                s[i][j]=s[i][j-1]+s[i-1][j]-s[i-1][j-1]+a[i][j];
            }
        for(int i=0;i<q;i++){
            int x1=sc.nextInt();
            int y1=sc.nextInt();
            int x2=sc.nextInt();
            int y2=sc.nextInt();
            System.out.printlns[(x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]);
        }

    }
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla