11.06算法学习打卡

约 1072 个字 24 行代码 预计阅读时间 4 分钟

前缀和的求取

一维前缀和

已知有一个数组a[n]，想要更快速地求出数组中某几项的和，我们可以先引入一个数组sum[n+1]，其中第n个元素sum[n]代表了数组a[n]第前n项的和

二维前缀和

有一个二维数组a[n][m]，想要求出其子矩阵的各项元素之和，首先明确：第sum[n][m]个前缀和为sum[n-1][m]+sum[n][m-1]-sum[n-1][m-1]+a[n][m]的结果。

现在给出两个坐标x1，y1;x2，y2(其中x1<x2,y1<y2)
要想求出夹在这两个坐标之间的子矩阵，则有如下式：
sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]

#include <iostream>
using namespace std;
#define LL long long
const LL N=1e3+9;
LL a[N][N];
LL sum[N][N];
int main() {
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++)
        cin>>a[i][j];
    }
    for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++)
        sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+a[i][j];
    }
    while(q--){
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1]<<endl;
    }
    return 0;
}

以下内容由deepseek生成：

一、二维前缀和时间复杂度总结

二维前缀和技术的核心思想是 “以空间换时间” 。它分为两个步骤：

1. 预处理
2. 查询

它们的时间复杂度是不同的。

操作	时间复杂度	空间复杂度	说明
预处理	O(m * n)	O(m * n)	其中 m 和 n 分别是二维矩阵的行数和列数。需要遍历整个原始矩阵一次，来构建前缀和矩阵 S。
单次区域求和查询	O(1)	O(1)	一旦预处理完成，计算任意子矩阵 [x1, y1] 到 [x2, y2] 的和只需要常数时间，通过一个公式即可得出：S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]。

核心优势： 当需要进行非常多次（例如 Q 次）的区域和查询时，二维前缀和的巨大优势就体现出来了。总时间复杂度为 O(m * n + Q)。

---

二、与暴力求和的对比

暴力求和是指不进行任何预处理，每次查询都直接遍历所求的子矩阵区域进行计算。

方面	二维前缀和	暴力求和
预处理时间	O(m * n)	O(1)（或无预处理）
单次查询时间	O(1)	O(k * l)
Q 次查询总时间	O(m * n + Q)	O(Q * k * l)
空间开销	O(m * n)（需要额外矩阵）	O(1)（不需要额外空间）
适用场景	需要频繁进行区域求和查询的场景，特别是查询次数 Q 很大时。	查询次数极少（例如只有一两次），或者矩阵本身是动态变化的（需要频繁更新矩阵元素的值）。

说明： * 在单次查询的时间复杂度中，k 和 l 分别是查询子矩阵的行数和列数。在最坏情况下（查询整个矩阵），k = m, l = n，单次查询复杂度为 O(m * n)。

---

三、直观对比与举例

假设我们有一个 1000 x 1000 的矩阵，并且需要进行 1,000,000 次随机子矩阵的和查询。

• 使用二维前缀和：

  1. 预处理： 耗时约为 1000 * 1000 = 1e6 次操作。
  2. 查询： 1,000,000 次查询，每次是 4 次加减运算（O(1)），总耗时约为 4 * 1e6 = 4e6 次操作。
  3. 总操作次数： 约 1e6 + 4e6 = 5e6 次。这在现代计算机上是可以轻松完成的。

• 使用暴力求和：

  • 我们假设每次查询的区域平均大小是 100 x 100。
  • 单次查询需要 100 * 100 = 10,000 次加法。
  • 1,000,000 次查询需要 1e6 * 1e4 = 1e10 次操作。
  • 总操作次数： 约 10,000,000,000 次。这比前缀和的方法慢了 2000倍！在实际编程中，如此大的计算量几乎必然会导致超时。

总结

特性	二维前缀和	暴力求和
效率	高效，适用于多次查询	低效，查询成本高
代价	需要额外的空间和一次性的预处理时间	无预处理，无额外空间
选择策略	“一次构建，多次使用”。当查询次数 Q 远大于 1 时，预处理的成本被均摊，总体效率远高于暴力。	“即用即算”。仅在查询极少或矩阵频繁变动时考虑。

结论：在解决需要快速计算二维区域和的问题时，如果查询操作非常频繁，二维前缀和是绝对的首选算法，它能将查询时间从 O(k*l) 优化到 O(1)，带来巨大的性能提升。 事情好多，快要忙不过来了

评论