[C++知识库]计蒜客-T1320-子矩阵求和

?

?解题技巧：

?

?

#include<bits/stdc++.h>
using namespace std;

//因为n*m<=100000，所以可能出现1*100000的极端情况，
//但是又不能开100000*100000的数组，所以要用到vector
vector<int>a[100005];

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            int k;
            cin>>k;
            a[i].push_back(k);
        }
    }

    //求二维数组前缀和

    //1、自己想的笨方法
//    for(int i=0;i<n;i++)
//    {
//        int row_cnt = 0;
//        for(int j=0;j<m;j++)
//        {
//            int pre_cnt = 0;
//            if(i>0&&j>=0)
//            {
//                pre_cnt = c[i-1][j];
//            }
//            row_cnt += a[i][j];
//            c[i].push_back(row_cnt + pre_cnt);
//        }
//    }

    //2、简单方法
    for(int i=0;i<n;i++)
    {
        for(int j=1;j<m;j++)
        {
            a[i][j]+=a[i][j-1];//先把这行前面的加到本格
        }
    }
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            a[i][j]+=a[i-1][j];//再把<=这列对应前面的行加到本格
        }
    }

    int q_num;
    cin>>q_num;
    for(int i=0;i<q_num;i++)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        int res = 0;
        res += a[x2-1][y2-1];
        //考虑边界情况决定加不加
        if(x1>1)
        {
            res-=a[x1-2][y2-1];
        }
        if(y1>1)
        {
            res-=a[x2-1][y1-2];
        }
        if(x1>1&&y1>1)
        {
            res += a[x1-2][y1-2];
        }
        cout<<res<<endl;
    }

    return 0;
}