二维前缀和问题

问题描述

今天在牛客上刷算法题时，碰到这样一道题，题目要求我们用前缀和解题，但是我并没有太深入了解过这个算法，于是只能暴力求解，但是发现提交后都显示超时或有些案例不通过，我百思不得其解，于是通过网上的搜索和看题解的方法终于对前缀和问题有了清晰的认识。
题目如下：

请你计算该子矩阵中全部元素之和，记为：

$$S(x1,y1,x2,y2)=\sum _{i=x1}^{x2}\sum _{j=y1}^{y2}{a}_{i,j}$$
这时候，二维前缀和 就派上用场了。

暴力解法

看到这题，最直观的想法就是：每次查询都遍历指定区域，把所有元素加起来。

import java.util.Scanner;public class ForceMatrix {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();int q = scanner.nextInt();int[][] matrix = new int[n + 1][m + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {matrix[i][j] = scanner.nextInt();}}for (int k = 0; k < q; k++) {int x1 = scanner.nextInt();int y1 = scanner.nextInt();int x2 = scanner.nextInt();int y2 = scanner.nextInt();// 暴力遍历指定区域long sum = 0;for (int i = x1; i <= x2; i++) {for (int j = y1; j <= y2; j++) {sum += matrix[i][j];}}System.out.println(sum);}scanner.close();}
}

暴力解法的问题

时间复杂度分析：
每次查询最坏需要遍历整个矩阵：O(n × m)，q 次查询总时间复杂度：O(q × n × m)，那么当 n = m = 10³，q = 10⁶ 时，总操作次数达到 10¹² 次，这是相当的耗时，所以我们要寻找优化方法。

前缀和优化

核心思想

与其每次查询都重新计算，不如先预处理出所有前缀和，让每次查询都能在 O(1) 时间内完成。

package com.coldscholor.prefix;import java.util.Scanner;/*** @author 寒士obj* @date 2025/08/10 21:34**/
// 2D前缀和
public class TwoPrefixSum1 {/*** 公式：s[i][j] = a[i][j] + s[i-1][j] + s[i][j-1] - s[i-1][j-1]* @param args*/public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int q = in.nextInt();long[][] a = new long[n + 1][m + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {a[i][j] = in.nextLong();}}long[][] sum = new long[n + 1][m + 1];for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {sum[i][j] = a[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];}}while (q-- > 0){int x1 = in.nextInt();int y1 = in.nextInt();int x2 = in.nextInt();int y2 = in.nextInt();System.out.println(sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]);}}
}

前缀和构建过程

假设我们有这样一个 3×3 矩阵：

原矩阵：
1  2  3
4  5  6  
7  8  9构建前缀和（每个位置存储从(1,1)到当前位置的矩形和）：
1   3   6
5  12  21
12 27  45

公式：prefix[i][j] = a[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1]

查询计算过程

要查询区域 (2,2) 到 (3,3) 的和：

目标区域：    需要的计算：2  3        prefix[3][3] = 45 (大矩形)5  6      - prefix[1][3] = 6  (上方多余)8  9      - prefix[3][1] = 12 (左方多余)  + prefix[1][1] = 1  (重复减去的左上角)= 45 - 6 - 12 + 1 = 28

目标区域是 (2,2) 到 (3,3)，即元素 5, 6, 8, 9之和为28，验证这个公式是正确的。

性能对比

方法	预处理时间	查询时间	总时间复杂度
暴力解法	O(1)	O(n×m)	O(q×n×m)
前缀和优化	O(n×m)	O(1)	O(n×m + q)

实际效果：
当 n = m = 1000, q = 100000 时，前缀和优化：10⁶ + 10⁵ ≈ 10⁶ 次操作（轻松AC）。