子矩阵求和

题目描述：

读入一个n*m的矩阵，q次询问，每次询问一个子矩阵内数字权值和。

输入格式：

第一行三个整数n，m，q

之后n行每行m个0到100的整数

之后q行，每行四个整数x1,y1,x2,y2，表示要询问的子矩阵。

输出格式：

q行表示答案。

样例输入1：

5 4 1

1 1 0 0

1 0 0 0

0 0 1 1

1 1 1 1

1 0 1 0

2 2 5 3

样例输出1：

4

约定：

1<=n，m<=500， q<=1000000

#include<cstdio>
#include<vector>
using namespace std;
vector<int> map[100100];
int main(){
    int N,M,Q,x;
    scanf("%d%d",&N,&M);
    scanf("%d",&Q);
    for(int i=0;i<=M;i++) map[0].push_back(0);//初始化
    for(int i=1;i<=N;i++){
        map[i].push_back(0);
        for(int j=1;j<=M;j++){
            scanf("%d",&x);
            map[i].push_back(map[i][j-1]+map[i-1][j]+x-map[i-1][j-1]);
        }
    }
    int x1,y1,x2,y2;
    while(Q--){
        scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
        int ans=map[x2][y2]-map[x2][y1-1]-map[x1-1][y2]+map[x1-1][y1-1];
        printf("%d
",ans);
    }
    return 0;
}