当前位置：首页 > news >正文

LeetCode算法日记 - Day 13: 前缀和、二维前缀和

news 2025/8/18 10:07:17

1. 前缀和

1.1 题目解析

1.2 解法

1.3 代码实现

2. 二维前缀和

2.1 题目解析

2.2 解法

2.3 代码实现

1. 前缀和

描述

对于给定的长度为 𝑛n 的数组 {𝑎1,𝑎2,…,𝑎𝑛}{a1,a2,…,an} ，我们有 𝑚m 次查询操作，每一次操作给出两个参数 𝑙,𝑟l,r ，你需要输出数组中第 𝑙l 到第 𝑟r 个元素之和，即 𝑎𝑙+𝑎𝑙+1+⋯+𝑎𝑟al+al+1+⋯+ar 。

输入描述：

第一行输入两个整数 𝑛,𝑚(1≦𝑛,𝑚≦105)n,m(1≦n,m≦105) 代表数组中的元素数量、查询次数。

第二行输入 𝑛n 个整数 𝑎1,𝑎2,…,𝑎𝑛(−109≦𝑎𝑖≦109)a1,a2,…,an(−109≦ai≦109) 代表初始数组。

此后 𝑚m 行，每行输入两个整数 𝑙,𝑟(1≦𝑙≦𝑟≦𝑛)l,r(1≦l≦r≦n) 代表一次查询。

输出描述：

对于每一次查询操作，在一行上输出一个整数，代表区间和。

示例1

输入：

复制输出：

3
6

1.1 题目解析

这道题的核心需求是：多次查询数组某个区间的元素之和。

如果我们每次都从头开始遍历区间求和，那么单次查询的复杂度是O(n)，在 m 次查询下会退化为 O(n*m)，数据上限是 10^5，这样会超时。
所以我们要寻找一种更快的“预处理 + 快速查询”的方式。

这里可以直接想到 前缀和：

预先计算好数组的前缀和 dp[i]，表示从下标 1 到 i 的元素和；
那么某个区间 [l, r] 的和只需要 dp[r] - dp[l-1]，时间复杂度瞬间降为 O(1)。
因此，总体复杂度是：
- 预处理：O(n)
- 查询：O(m)
- 总复杂度：O(n+m)，完全可行。

1.2 解法

i）定义前缀和数组
设 dp[i] 表示数组前 i 个元素的和：

dp[i]=a1+a2+⋯+ai

递推式：

dp[i]=dp[i−1]+arr[i]

ii）区间和公式
当我们要查询 [l, r] 区间的和时：

sum(l,r)=dp[r]−dp[l−1]

dp[r] 表示 [1, r] 的和
dp[l-1] 表示 [1, l-1] 的和
相减即可得到 [l, r] 的和

iii）复杂度分析

预处理前缀和：O(n)
每次查询：O(1)
总复杂度：O(n + m)，完全可以在限制内高效运行。

1.3 代码实现

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n = scan.nextInt(); // 数组长度int m = scan.nextInt(); // 查询次数int[] arr = new int[n + 1];   // 原始数组 (1-based)long[] dp = new long[n + 1];  // 前缀和数组// 输入数组for (int i = 1; i <= n; i++) {arr[i] = scan.nextInt();}// 构建前缀和for (int i = 1; i <= n; i++) {dp[i] = dp[i - 1] + arr[i];}// 处理查询while (m-- > 0) {int l = scan.nextInt();int r = scan.nextInt();System.out.println(dp[r] - dp[l - 1]);}}
}

2. 二维前缀和

描述

给定一个由 𝑛n 行 𝑚m 列整数组成的矩阵 {𝑎𝑖,𝑗}{ai,j}（下标均从 11 开始）。
现有 𝑞q 次独立查询，第 𝑘k 次查询给定四个整数 𝑥1,𝑦1,𝑥2,𝑦2x1,y1,x2,y2，表示左上角坐标 (𝑥1,𝑦1)(x1,y1) 与右下角坐标 (𝑥2,𝑦2)(x2,y2) 满足 1≦𝑥1≦𝑥2≦𝑛1≦x1≦x2≦n 且 1≦𝑦1≦𝑦2≦𝑚1≦y1≦y2≦m。
请你计算该子矩阵中全部元素之和，记为

S(𝑥1,𝑦1,𝑥2,𝑦2)=∑𝑖=𝑥1𝑥2 ∑𝑗=𝑦1𝑦2𝑎𝑖,𝑗

你需要依次回答所有查询。

输入描述：

在一行上输入三个整数 𝑛,𝑚,𝑞(1≦𝑛,𝑚≦103; 1≦𝑞≦105)n,m,q(1≦n,m≦103; 1≦q≦105)，依次表示矩阵的行数、列数与查询次数。
此后 𝑛n 行，每行输入 𝑚m 个整数 𝑎𝑖,1,𝑎𝑖,2,…,𝑎𝑖,𝑚(−109≦𝑎𝑖,𝑗≦109)ai,1,ai,2,…,ai,m(−109≦ai,j≦109)，表示矩阵第 𝑖i 行的元素；共计 𝑛×𝑚n×m 个整数。
此后 𝑞q 行，每行输入四个整数 𝑥1,𝑦1,𝑥2,𝑦2x1,y1,x2,y2，所有变量均满足

1≦𝑥1≦𝑥2≦𝑛,1≦𝑦1≦𝑦2≦𝑚1

输出描述：

对于每一次查询，在一行上输出一个整数，表示对应子矩阵元素之和。

示例1

输入：

复制输出：

8
25
32

2.1 题目解析

题目本质

这道题的本质就是 “多次查询一个子矩阵的元素和”。
换句话说，我们需要在一个二维矩阵上，频繁地求局部和。

常规解法

最直观的方法：每次查询时，枚举子矩阵 (x1,y1)→(x2,y2)把里面所有数加起来。

问题分析

如果子矩阵大小接近 n×m，一次查询复杂度就是 O(nm)。
在最坏情况下：n=m=1000, q=10^5

枚举每个子矩阵元素，复杂度约为 10^{11} → 必然超时。

思路转折

要想高效，就必须 在查询前进行预处理。
类比一维数组的 前缀和：

一维前缀和把“区间和查询”优化到 O(1)O(1)O(1)。
同理，二维前缀和可以把“子矩阵和查询”优化到 O(1)O(1)O(1

2.2 解法

i）构建二维前缀和矩阵 dp[i][j]，表示从 (1,1)(1,1)(1,1) 到 (i,j)(i,j)(i,j) 子矩阵内所有元素的和。

ii）递推公式：

dp[i][j]=dp[i−1][j]+dp[i][j−1]−dp[i−1][j−1]+a[i][j]

iii）查询子矩阵和公式（容斥原理）：

S(x1,y1,x2,y2)=dp[x2][y2]−dp[x1−1][y2]−dp[x2][y1−1]+dp[x1−1][y1−1]

步骤拆解

输入矩阵 → 读入 n×m 的二维数组。
构建前缀和矩阵 → 用递推公式预处理。
处理查询 → 每个查询用容斥公式计算子矩阵和。
输出结果 → 每次查询 O(1)O(1)O(1)。

2.3 代码实现

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();   // 行数int m = in.nextInt();   // 列数int q = in.nextInt();   // 查询次数int[][] arr = new int[n + 1][m + 1];long[][] dp = new long[n + 1][m + 1];// 读入矩阵for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {arr[i][j] = in.nextInt();}}// 构建二维前缀和for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + arr[i][j];}}// 处理查询while (q-- > 0) {int x1 = in.nextInt();int y1 = in.nextInt();int x2 = in.nextInt();int y2 = in.nextInt();long ans = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];System.out.println(ans);}}
}

查看全文

http://www.lryc.cn/news/623793.html