思路

1. 求前缀和：s[i][j]=s[i-1][j]+s[i][j-1]+x-s[i-1][j-1]
2. 用前缀和：对于(x1,y1),(x2,y2)
   1. sum=s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]

c++

用时 大约657ms

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1010;

int preSum[N][N];
int n,m,q;

int main(){
    scanf("%d%d%d",&n,&m,&q);
    //求前缀和
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int x;
            scanf("%d",&x);
            preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]+x-preSum[i-1][j-1];
        }
    }
    //用前缀和
    while(q--){
        int x1,y1,x2,y2;
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        printf("%d\n",preSum[x2][y2]-preSum[x1-1][y2]-preSum[x2][y1-1]+preSum[x1-1][y1-1]);
    }
    return 0;
}

java

用时 大约3787s

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args) throws Exception{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(new OutputStreamWriter(System.out));
        String[] s1=br.readLine().split(" ");
        int n=Integer.parseInt(s1[0]),m=Integer.parseInt(s1[1]),q=Integer.parseInt(s1[2]);
        //求前缀和
        int[][] arr=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            String[] s2=br.readLine().split(" ");
            for(int j=1;j<=m;j++) {
                int x=Integer.parseInt(s2[j-1]);
                arr[i][j]=arr[i-1][j]+arr[i][j-1]-arr[i-1][j-1]+x;

            }
        }
        //用前缀和
        while(q>0){
            q--;
            String[] s3=br.readLine().split(" ");
            int x1=Integer.parseInt(s3[0]),y1=Integer.parseInt(s3[1]),x2=Integer.parseInt(s3[2]),y2=Integer.parseInt(s3[3]);
            pw.println(arr[x2][y2]-arr[x1-1][y2]-arr[x2][y1-1]+arr[x1-1][y1-1]);
        }
        pw.flush();
    }
}

python

用时 大约5518ms

n,m,q=map(int,input().split())
#求前缀和
preSum=[[0 for j in range(m+5)] for i in range(n+5)]
for i in range(1,n+1):
    line=input()
    row=[int(i) for i in line.split()]
    for j in range(1,m+1):
        preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]+row[j-1]-preSum[i-1][j-1]

#用前缀和
for i in range(q):
    x1,y1,x2,y2=map(int,input().split())
    print(preSum[x2][y2]-preSum[x1-1][y2]-preSum[x2][y1-1]+preSum[x1-1][y1-1])