前缀和算法模板

简介: 前缀和算法模板

一维前缀和

算法用途:快速求出数组中某一连续区间的和

一维前缀和算法模板

1、预处理出一个 dp 数组

要求原数组存储在 n + 1 的空间大小中,其中后 n 个空间存数据。

dp数组,数组开 n + 1个空间,dp[i] 表示 [ 1, i ] 区间内所有元素的和

处理方法:  dp[ i ] = dp[ i - 1 ] + arr[ i ] 

2、使用前缀和数组

区间 l 到 r 的和: sum = dp[ r ] - dp[ l - 1 ]

复杂度分析

处理前缀和数组,需要 O(N) 的空间复杂度和空间复杂度,求一次区间 l 到 r 的和,需要 O(1) 的时间复杂度,如果需要求 q 次和,则时间复杂度就是 O(q) + O(N)

二维前缀和

算法用途:快速求出某个子矩阵的和

二维前缀和算法模板

1、预处理出一个 前缀和矩阵(二维数组 dp)

假设原矩阵有 m 行,n列,那么这个前缀和矩阵的二维数组 dp 要开 m+1 行, n+1 列的空间,第一行,第一列的数据都为 0, dp[ i ][ j ] 表示 [ 1, i ] 行,[ 1, j ] 列包含的这个矩阵的数据和

处理方法:dp[ i ][ j ] = dp[ i - 1 ][ j ] + dp[ i ][ j - 1 ] - dp[ i - 1 ][ j - 1 ] + arr[ i ][ j ]

2、使用前缀和矩阵

[ x1, y1 ] ~ [ x2, y2 ] = dp[ x2, y2] - dp[ x1- 1 ][ y2 ] - dp[ x2 ][ y2 - 1 ] + dp[ x1 ][ y1 ]

二维数组前缀和的建立和使用图解

注:vector开具体大小空间的定义方式

一维 vector :vector< int > dp ( m + 1 ) 开 m + 1 个连续的空间

二维 vector :vector< vector< int > > dp(n + 1, vector<int> (m + 1)) (n+1行,m + 1列的二维数组定义方式)

相关文章
|
3月前
|
算法
【算法】前缀和——二维前缀和模板题
【算法】前缀和——二维前缀和模板题
|
3月前
|
算法
【算法】前缀和——前缀和
【算法】前缀和——前缀和
|
2月前
|
存储 算法 Java
前缀和算法
本文介绍了前缀和及其变种在解决区间求和问题中的应用。首先,一维前缀和可通过预处理数组快速求得任意区间的和。接着,二维前缀和扩展了这一思想,适用于矩阵操作。此外,文章探讨了如何利用前缀和解决诸如“寻找数组中心下标”、“除自身以外数组的乘积”等问题,并进一步讲解了涉及哈希表优化的“和为 K 的子数组”等相关题目。最后,通过实例展示了如何在矩阵中高效计算特定区域的元素之和。文中包含代码示例与图解说明,便于理解。
41 0
前缀和算法
|
1月前
|
人工智能 算法 C++
一篇带你速通前缀和算法(C/C++)
一篇带你速通前缀和算法(C/C++)
|
4月前
|
人工智能 算法 JavaScript
【算法】前缀和与差分
算法学习——前缀和与差分(含一维和二维)
51 4
【算法】前缀和与差分
|
3月前
|
算法 C++
【算法】前缀和算法——和可被K整除的子数组
【算法】前缀和算法——和可被K整除的子数组
|
3月前
|
算法
【算法】前缀和算法——和为k的子数组之和
【算法】前缀和算法——和为k的子数组之和
|
3月前
|
算法
【算法】前缀和——除自身以外数组的乘积
【算法】前缀和——除自身以外数组的乘积
|
3月前
|
算法
【算法】前缀和——寻找数组的中心下标
【算法】前缀和——寻找数组的中心下标
|
5月前
|
算法 Java 数据处理
Java算法模板 数据流快读
Java算法模板 数据流快读
36 2