分行做前綴和，再把直的前綴和加起來。

就是橫的做一次，直的做一次的意思。

這樣下來，二次前綴和陣列的[x][y]就會是原本陣列的[0][0]到[x][y]這整塊。

接下來，就可以用簡單的排容原理來得出任意區塊的總和了!(如果想不出來可以試著畫圖理解)

這樣的複雜度只有O(n*n+m)

比只做一次前綴和的O(n*n+m*n)

以及暴力加法的O(m*n*n)還快

(只做一次好像也會過就是了...)

然後是我的範例(把註解取消掉可以更了解原理)

#include<bits/stdc++.h>

using namespace std;

//template<class T>
//ostream& operator<<(ostream& os,vector<T> v)
//{
//    os<<" ";
//    for(int i=0; i<v.size(); i++)
//    {
//        os<<v[i]<<" ";
//    }
//    os<<"\n";
//    return os;
//}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n,m,tmp;
    pair<int,int> a,b;
    vector<vector<int>> v;
    vector<vector<int>> p;
    while( cin>>n>>m)
    {
        v.clear();
        p.clear();
        vector<int> s(n);
        v.push_back(s);
        p.push_back(s);
        for(int i=1; i<=n; i++)
        {
            v.push_back({0});
            p.push_back({0});
            for(int j=1; j<=n; j++)
            {
                cin>>tmp;
                v[i].push_back(tmp);
                p[i].push_back(v[i][j]+p[i][j-1]);
            }
        }
        for(int i=0; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                p[j][i]+=p[j-1][i];
            }
        }
        //cout<<"\n"<<v;
        //cout<<"\n"<<p;
        for(int i=0; i<m; i++)
        {
            cin>>a.first>>a.second>>b.first>>b.second;
            cout<<p[b.first][b.second]-p[a.first-1][b.second]-p[b.first][a.second-1]+p[a.first-1][a.second-1]<<"\n";
        }
    }
    return 0;
}