题目链接

【模板】二维前缀和

题目描述

给定一个 行 列的矩阵，有 次查询，每次查询给定一个子矩阵的左上角坐标 和右下角坐标 ，求该子矩阵中所有元素的和。

解题思路

本题是典型的二维区间求和问题，可以使用二维前缀和的方法高效解决。

一维前缀和是求解序列中任意区间和的有效方法，其核心思想是预处理一个前缀和数组 ，其中 记录了序列前 个元素的和。这样，区间 的和就可以通过 在 的时间内计算出来。

二维前缀和是一维前缀和思想在二维矩阵上的扩展。我们同样可以预处理一个二维前缀和矩阵 ，其中 记录了以 为左上角， 为右下角的子矩阵中所有元素的和。

的递推计算公式为：

其中， 是原矩阵在 位置的元素值。

这个公式的几何意义是： 处的总和等于其上方矩形的和加上其左方矩形的和，再减去左上方被重复计算的矩形的和，最后加上当前元素的值。

在计算出整个前缀和矩阵后，对于任意一个以 为左上角、 为右下角的子矩阵，其元素和可以通过以下公式在 的时间内求出：

这个公式的几何意义是：目标子矩阵的和等于以 为右下角的整个大矩形的和，减去其上方多余矩形的和，再减去其左方多余矩形的和，最后加上左上方被重复减去的矩形的和。

为了方便处理边界情况（如 或 ），通常将前缀和矩阵的下标从 1 开始，大小设为 ，并初始化为 0。

由于题目提到数据量可能很大，需要注意使用快速输入输出。同时，矩阵元素之和可能会超过 int 类型的范围，因此前缀和矩阵建议使用 long long（C++）或 long（Java）类型来存储，以防止溢出。

代码

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // 快速输入输出
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, q;
    cin >> n >> m >> q;

    // 前缀和矩阵 s[i][j] 记录的是以 (1,1) 为左上角，(i,j) 为右下角的矩阵和
    // 使用 long long 防止求和溢出
    vector<vector<long long>> s(n + 1, vector<long long>(m + 1, 0));

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int a;
            cin >> a;
            // 递推计算前缀和
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a;
        }
    }

    // 处理每次查询
    while (q--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        // O(1) 计算子矩阵和
        long long sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
        cout << sum << "\n";
    }

    return 0;
}

import java.util.Scanner;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        // 由于Java的Scanner较慢，对于大数据量使用StreamTokenizer进行快速读入
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        
        in.nextToken();
        int n = (int)in.nval;
        in.nextToken();
        int m = (int)in.nval;
        in.nextToken();
        int q = (int)in.nval;

        // 前缀和矩阵 s[i][j] 记录的是以 (1,1) 为左上角，(i,j) 为右下角的矩阵和
        long[][] s = new long[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                in.nextToken();
                int a = (int)in.nval;
                // 递推计算前缀和
                s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a;
            }
        }

        StringBuilder sb = new StringBuilder();
        // 处理每次查询
        for (int i = 0; i < q; i++) {
            in.nextToken();
            int x1 = (int)in.nval;
            in.nextToken();
            int y1 = (int)in.nval;
            in.nextToken();
            int x2 = (int)in.nval;
            in.nextToken();
            int y2 = (int)in.nval;
            // O(1) 计算子矩阵和
            long sum = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
            sb.append(sum).append("\n");
        }
        System.out.print(sb.toString());
    }
}

import sys

# 快速输入
input = sys.stdin.readline

def solve():
    n, m, q = map(int, input().split())

    # 前缀和矩阵 s[i][j] 记录的是以 (1,1) 为左上角，(i,j) 为右下角的矩阵和
    s = [[0] * (m + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        # 逐行读取输入
        row_input = list(map(int, input().split()))
        for j in range(1, m + 1):
            # 递推计算前缀和
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + row_input[j-1]
    
    # 处理每次查询
    answers = []
    for _ in range(q):
        x1, y1, x2, y2 = map(int, input().split())
        # O(1) 计算子矩阵和
        sum_val = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]
        answers.append(str(sum_val))
    
    print("\n".join(answers))

solve()

算法及复杂度

  • 算法：二维前缀和
  • 时间复杂度：预处理时间为 ，每次查询时间为 ，因此总时间复杂度为 。
  • 空间复杂度：需要一个二维数组来存储前缀和，因此空间复杂度为 。