题解 | #【模板】二维前缀和#

思路是用一个二维数组sum来储存(0, 0)到该点所形成的子矩阵中所有数的和。即sum.at(i).at(j)储存着以(0,0)(i,j)为反对角线的矩阵的所有元素的和。
当要计算(x1, y1)与(x2, y2)所形成的矩阵中所有元素的和时，只需要用(0, 0)(x2, y2)这个大的矩形，减去(0, 0)(x1 - 1, y2)和(0, 0)(x2, y1 - 1)这两个矩形。当x1或y1为0时需分类讨论。

这种做法的时间复杂度主要体现在建立sum数组上，建立sum时用到了三重循环，时间复杂度在O(nm)之上。空间复杂度为O(nm)。
时间复杂度过高这个问题在提交时暴露无遗。此时我开始意识到我的做法可能出问题了。

但是在看了别的同学的做法后发现思路基本一直，仅在实现的具体细节上有所差异。可能确实是代码中有些冗余，且没有选择效率较高的写法，还有优化空间。

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n, m, q;
    cin >> n >> m >>q;
    vector<int> col(m, 0);
    vector<vector<int>> matrix(n,col);
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            cin >> matrix.at(i).at(j);
        }
    }
    vector<long long> scol(m, 0);
    vector<vector<long long>> sum(n,scol);
    for(int i = 0;i < n;i++){
        for(int j = 0;j < m;j++){
            if(j == 0 && i == 0){
                sum.at(i).at(j) = matrix.at(i).at(j);
            }
            else if(i == 0){
                sum.at(i).at(j) = sum.at(i).at(j - 1) + matrix.at(i).at(j);
            }
            else if(j == 0){
                sum.at(i).at(j) = sum.at(i - 1).at(j) + matrix.at(i).at(j);
            }
            else{
                sum.at(i).at(j) = sum.at(i).at(j - 1);
                for(int k = 0;k < i + 1;k++){
                    sum.at(i).at(j) += matrix.at(k).at(j);
                }
            }
        }
    }
    for(int i = 0;i < q;i++){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        x1--;
        y1--;
        x2--;
        y2--;
        long long res;
        if(x1 == x2 && y1 == y2){
            res = matrix.at(x1).at(y1);
        }
        else if(!x1 && !y1){
            res = sum.at(x2).at(y2);
        }
        else if(x1 && !y1){
            res = sum.at(x2).at(y2) - sum.at(x1 - 1).at(y2);
        }
        else if(!x1 && y1){
            res = sum.at(x2).at(y2) - sum.at(x2).at(y1 - 1);
        }
        else if(x1 && y1){
            res = sum.at(x2).at(y2) - sum.at(x2).at(y1 - 1) - sum.at(x1 - 1).at(y2) + sum.at(x1 - 1).at(y1 - 1);
        }
        cout << res << endl;
    }
    return 0;
}