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

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);  // 优化输入输出
    cin.tie(0);
    
    int n, m, q;
    cin >> n >> m >> q;
    
    // 构建二维前缀和数组，多加一行一列便于计算
    vector<vector<long long>> prefix(n + 1, vector<long long>(m + 1, 0));
    
    // 读入矩阵并计算前缀和
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            int x;
            cin >> x;
            // 二维前缀和公式
            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + x;
        }
    }
    
    // 处理查询
    while(q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        // 计算子矩阵的和
        long long sum = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1];
        cout << sum << "\n";
    }
    
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        String[] line = br.readLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int m = Integer.parseInt(line[1]);
        int q = Integer.parseInt(line[2]);
        
        // 构建二维前缀和数组
        long[][] prefix = new long[n + 1][m + 1];
        
        // 读入矩阵并计算前缀和
        for(int i = 1; i <= n; i++) {
            line = br.readLine().split(" ");
            for(int j = 1; j <= m; j++) {
                int x = Integer.parseInt(line[j-1]);
                prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + x;
            }
        }
        
        // 处理查询
        while(q-- > 0) {
            line = br.readLine().split(" ");
            int x1 = Integer.parseInt(line[0]);
            int y1 = Integer.parseInt(line[1]);
            int x2 = Integer.parseInt(line[2]);
            int y2 = Integer.parseInt(line[3]);
            
            long sum = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1];
            out.println(sum);
        }
        
        out.flush();
        br.close();
    }
}

def main():
    # 读取输入
    n, m, q = map(int, input().split())
    
    # 构建二维前缀和数组
    prefix = [[0] * (m + 1) for _ in range(n + 1)]
    
    # 读入矩阵并计算前缀和
    for i in range(1, n + 1):
        row = list(map(int, input().split()))
        for j in range(1, m + 1):
            prefix[i][j] = prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1] + row[j-1]
    
    # 处理查询
    for _ in range(q):
        x1, y1, x2, y2 = map(int, input().split())
        # 计算子矩阵的和
        sum_region = prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]
        print(sum_region)

if __name__ == "__main__":
    main()