首页 最新 热门 推荐

  • 首页
  • 最新
  • 热门
  • 推荐

算法每日双题精讲 —— 前缀和(【模板】一维前缀和,【模板】二维前缀和)

  • 25-02-17 11:20
  • 2229
  • 8712
blog.csdn.net

在算法竞赛与日常编程中,前缀和是一种极为实用的预处理技巧,能显著提升处理区间和问题的效率。今天,我们就来深入剖析一维前缀和与二维前缀和这两个经典模板。

一、【模板】一维前缀和

题目描述

给定一个长度为 n n n 的整数数组 a a a,我们需要完成以下两个任务:

  1. 预处理数组,得到前缀和数组。
  2. 能够快速查询数组中任意区间 [ l , r ] [l, r] [l,r]( 0 ≤ l ≤ r < n 0 \leq l \leq r < n 0≤l≤r<n)内所有元素的和。

算法原理

一维前缀和的核心思想是预先计算数组中每个位置之前所有元素的总和。设前缀和数组为 s s s,其中 s [ i ] s[i] s[i] 表示数组 a a a 中前 i i i 个元素的和( i i i 从 1 1 1 开始),那么有递推公式:
[s[i] = s[i - 1]+a[i - 1]]
这里 s [ 0 ] = 0 s[0]=0 s[0]=0,是为了方便处理边界情况。

当我们需要查询区间 [ l , r ] [l, r] [l,r] 的和时,根据前缀和的性质,该区间的和可以通过 s [ r + 1 ] − s [ l ] s[r + 1]-s[l] s[r+1]−s[l] 快速得到。这是因为 s [ r + 1 ] s[r + 1] s[r+1] 包含了前 r + 1 r + 1 r+1 个元素的和, s [ l ] s[l] s[l] 包含了前 l l l 个元素的和,两者相减就得到了区间 [ l , r ] [l, r] [l,r] 的和。

在这里插入图片描述

在这里插入图片描述

C++ 代码实现

#include 
#include 

using namespace std;

// 计算一维前缀和数组
vector<int> calculatePrefixSum(const vector<int>& a) {
    int n = a.size();
    vector<int> s(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i - 1] + a[i - 1];
    }
    return s;
}

// 查询区间 [l, r] 的和
int querySum(const vector<int>& s, int l, int r) {
    return s[r + 1] - s[l];
}

int main() {
    vector<int> a = {1, 2, 3, 4, 5};
    vector<int> s = calculatePrefixSum(a);

    int l = 1, r = 3;
    cout << "The sum of the interval [" << l << ", " << r << "] is: " << querySum(s, l, r) << endl;

    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

复杂度分析

  • 时间复杂度:计算前缀和数组的时间复杂度为 O ( n ) O(n) O(n),因为需要遍历数组一次。每次查询区间和的时间复杂度为 O ( 1 ) O(1) O(1),这使得在多次查询的场景下,一维前缀和算法具有很高的效率。
  • 空间复杂度:需要额外的长度为 n + 1 n + 1 n+1 的数组来存储前缀和,因此空间复杂度为 O ( n ) O(n) O(n)。

二、【模板】二维前缀和

题目描述

给定一个 m × n m \times n m×n 的二维整数矩阵 A A A,我们要完成以下任务:

  1. 预处理矩阵,得到二维前缀和矩阵。
  2. 能够快速查询矩阵中任意子矩阵 [ ( x 1 , y 1 ) , ( x 2 , y 2 ) ] [(x_1, y_1), (x_2, y_2)] [(x1​,y1​),(x2​,y2​)]( 0 ≤ x 1 ≤ x 2 < m 0 \leq x_1 \leq x_2 < m 0≤x1​≤x2​<m, 0 ≤ y 1 ≤ y 2 < n 0 \leq y_1 \leq y_2 < n 0≤y1​≤y2​<n)内所有元素的和。

算法原理

对于二维前缀和,我们定义 S [ i ] [ j ] S[i][j] S[i][j] 表示矩阵 A A A 中从左上角 ( 0 , 0 ) (0, 0) (0,0) 到右下角 ( i − 1 , j − 1 ) (i - 1, j - 1) (i−1,j−1) 这个子矩阵内所有元素的和( i i i 和 j j j 从 1 1 1 开始)。其递推公式如下:
S [ i ] [ j ] = S [ i − 1 ] [ j ] + S [ i ] [ j − 1 ] − S [ i − 1 ] [ j − 1 ] + A [ i − 1 ] [ j − 1 ] S[i][j]=S[i - 1][j]+S[i][j - 1]-S[i - 1][j - 1]+A[i - 1][j - 1] S[i][j]=S[i−1][j]+S[i][j−1]−S[i−1][j−1]+A[i−1][j−1]
这里减去 S [ i − 1 ] [ j − 1 ] S[i - 1][j - 1] S[i−1][j−1] 是为了避免重复计算。

当查询子矩阵 [ ( x 1 , y 1 ) , ( x 2 , y 2 ) ] [(x_1, y_1), (x_2, y_2)] [(x1​,y1​),(x2​,y2​)] 的和时,公式为:
s u m = S [ x 2 + 1 ] [ y 2 + 1 ] − S [ x 1 ] [ y 2 + 1 ] − S [ x 2 + 1 ] [ y 1 ] + S [ x 1 ] [ y 1 ] sum = S[x_2 + 1][y_2 + 1]-S[x_1][y_2 + 1]-S[x_2 + 1][y_1]+S[x_1][y_1] sum=S[x2​+1][y2​+1]−S[x1​][y2​+1]−S[x2​+1][y1​]+S[x1​][y1​]

在这里插入图片描述

在这里插入图片描述

C++ 代码实现

#include 
#include 

using namespace std;

// 计算二维前缀和矩阵
vector<vector<int>> calculateTwoDPrefixSum(const vector<vector<int>>& A) {
    int m = A.size();
    int n = A[0].size();
    vector<vector<int>> S(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i - 1][j - 1];
        }
    }
    return S;
}

// 查询子矩阵 [(x1, y1), (x2, y2)] 的和
int queryTwoDSum(const vector<vector<int>>& S, int x1, int y1, int x2, int y2) {
    return S[x2 + 1][y2 + 1] - S[x1][y2 + 1] - S[x2 + 1][y1] + S[x1][y1];
}

int main() {
    vector<vector<int>> A = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
    vector<vector<int>> S = calculateTwoDPrefixSum(A);

    int x1 = 0, y1 = 0, x2 = 1, y2 = 1;
    cout << "The sum of the sub - matrix [(" << x1 << ", " << y1 << "), (" << x2 << ", " << y2 << ")] is: "
         << queryTwoDSum(S, x1, y1, x2, y2) << endl;

    return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

复杂度分析

  • 时间复杂度:计算二维前缀和矩阵需要两层嵌套循环遍历矩阵,时间复杂度为 O ( m × n ) O(m \times n) O(m×n)。每次查询子矩阵和的时间复杂度为 O ( 1 ) O(1) O(1),这使得在多次查询子矩阵和的场景下,二维前缀和算法非常高效。
  • 空间复杂度:需要额外的 ( m + 1 ) × ( n + 1 ) (m + 1)\times(n + 1) (m+1)×(n+1) 大小的矩阵来存储二维前缀和,因此空间复杂度为 O ( m × n ) O(m \times n) O(m×n)。

通过以上的讲解和代码实现,我们可以看到前缀和算法在处理区间和与子矩阵和问题时的强大威力。它通过预处理的方式,将原本可能需要 O ( n ) O(n) O(n) 或 O ( m × n ) O(m\times n) O(m×n) 时间复杂度的查询操作优化到了 O ( 1 ) O(1) O(1),在实际应用中能显著提升程序的性能。希望大家能够熟练掌握这两个模板,并在后续的算法学习和实践中灵活运用。

注:本文转载自blog.csdn.net的A charmer的文章"https://blog.csdn.net/2301_82213854/article/details/145389850"。版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。如有侵权,请联系我们删除。
复制链接
复制链接
相关推荐
发表评论
登录后才能发表评论和回复 注册

/ 登录

评论记录:

未查询到任何数据!
回复评论:

分类栏目

后端 (14832) 前端 (14280) 移动开发 (3760) 编程语言 (3851) Java (3904) Python (3298) 人工智能 (10119) AIGC (2810) 大数据 (3499) 数据库 (3945) 数据结构与算法 (3757) 音视频 (2669) 云原生 (3145) 云平台 (2965) 前沿技术 (2993) 开源 (2160) 小程序 (2860) 运维 (2533) 服务器 (2698) 操作系统 (2325) 硬件开发 (2492) 嵌入式 (2955) 微软技术 (2769) 软件工程 (2056) 测试 (2865) 网络空间安全 (2948) 网络与通信 (2797) 用户体验设计 (2592) 学习和成长 (2593) 搜索 (2744) 开发工具 (7108) 游戏 (2829) HarmonyOS (2935) 区块链 (2782) 数学 (3112) 3C硬件 (2759) 资讯 (2909) Android (4709) iOS (1850) 代码人生 (3043) 阅读 (2841)

热门文章

113
数据结构与算法
关于我们 隐私政策 免责声明 联系我们
Copyright © 2020-2025 蚁人论坛 (iYenn.com) All Rights Reserved.
Scroll to Top