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

【模板】二维前缀和

https://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc

解题思路

问题分析：
- 需要多次查询矩阵子区域的和
- 直接累加会导致时间复杂度 $\mathcal{O}(n*m*q)$
- 可以使用二维前缀和优化到 $\mathcal{O}(n*m + q)$
二维前缀和优化：
- 预处理矩阵，计算二维前缀和
- 对于查询 $(x1,y1,x2,y2)$ ，结果为： $prefix[x2][y2] - prefix[x1-1][y2] - prefix[x2][y1-1] + prefix[x1-1][y1-1]$
- 预处理时间 $\mathcal{O}(n*m)$ ，每次查询 $\mathcal{O}(1)$
实现要点：
- 注意前缀和可能超出 $\text{int}$ 范围，使用 $\text{long long}$
- 注意输入的下标从 $1$ 开始
- 使用快速输入输出优化读写时间

代码

c++
java
python

#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()