C++中前綴和數(shù)組(算法)基本介紹
1.前言
如何快速求得一個(gè)數(shù)組的前綴和?
1. 1 前綴和的基本概念
前綴和(Prefix Sum)是指數(shù)組中某個(gè)位置之前的所有元素的和。對(duì)于數(shù)組arr
,其前綴和數(shù)組prefixSum
定義為:
prefixSum[0] = 0
prefixSum[i] = prefixSum[i-1] + arr[i-1]
(對(duì)于i > 0
)- 這樣,任意子數(shù)組
arr[l...r]
的和可以通過(guò)prefixSum[r+1] - prefixSum[l]
快速計(jì)算出來(lái)。
2.一維數(shù)組的前綴和
在處理數(shù)組區(qū)間和問(wèn)題時(shí),前綴和(Prefix Sum)是一個(gè)非常有效的工具,可以大大加快查詢(xún)速度。下面詳細(xì)解釋如何預(yù)處理前綴和數(shù)組,并使用前綴和數(shù)組快速計(jì)算任意區(qū)間的元素和。
步驟一:預(yù)處理前綴和數(shù)組
給定一個(gè)數(shù)組arr
,長(zhǎng)度為n
,我們可以預(yù)處理一個(gè)前綴和數(shù)組dp
,其中dp[i]
表示數(shù)組arr
從索引1
到索引i
的所有元素的和。
初始化dp[0] = 0
(這是為了方便計(jì)算從索引1
開(kāi)始的區(qū)間和)。
使用遞推公式dp[i] = dp[i - 1] + arr[i - 1]
來(lái)計(jì)算dp
數(shù)組的每個(gè)元素。注意,這里arr
的索引從0
開(kāi)始,而dp
的索引
從1
開(kāi)始模擬區(qū)間[1, i]
。//從1開(kāi)始是為了避免從0開(kāi)始時(shí)會(huì)出現(xiàn)-1,從而進(jìn)行判斷,減少?gòu)?fù)雜邊界情況
1 2 3 4 5
0 | 1 | 2 | 3 | 4 | 5 |
!!!此步是為了處理邊界情況
具體代碼如下:
std::vector<int> dpsum(const vector<int>& arr) { int n = arr.size(); vector<int> dp(n + 1, 0); // dp 數(shù)組的長(zhǎng)度是 n+1,并初始化為 0 for (int i = 1; i <= n; ++i) { dp[i] = dp[i - 1] + arr[i - 1]; } return dp; }
步驟二:使用前綴和數(shù)組快速計(jì)算區(qū)間和
給定一個(gè)區(qū)間[l, r]
,我們可以利用預(yù)處理好的前綴和數(shù)組dp
快速計(jì)算區(qū)間內(nèi)所有元素的和。
區(qū)間[l, r]
內(nèi)所有元素的和為dp[r] - dp[l - 1]
。
具體解釋如下:
dp[r]
包含從索引1
到索引r
的所有元素的和。dp[l - 1]
包含從索引1
到索引l - 1
的所有元素的和。- 因此,
dp[r] - dp[l - 1]
正好是區(qū)間[l, r]
內(nèi)所有元素的和。
具體代碼如下:
int queryRangeSum(const vector<int>& dp, int l, int r) { return dp[r] - dp[l - 1]; }
下面展示一個(gè)一維數(shù)組前綴和模板
#include <iostream> #include <vector> using namespace std; // 預(yù)處理前綴和數(shù)組的函數(shù) vector<int> dpSum(const vector<int>& arr) { int n = arr.size(); std::vector<int> dp(n + 1, 0); // dp 數(shù)組的長(zhǎng)度是 n+1,并初始化為 0 for (int i = 1; i <= n; ++i) { dp[i] = dp[i - 1] + arr[i - 1]; } return dp; } // 查詢(xún)區(qū)間和的函數(shù) int queryRangeSum(const vector<int>& dp, int l, int r) { return dp[r] - dp[l - 1]; } int main() { // 示例數(shù)組 vector<int> arr = {1, 2, 3, 4, 5}; // 預(yù)處理前綴和數(shù)組 vector<int> dp = dpSum(arr); // 查詢(xún)區(qū)間 [2, 4] 的和(注意C++中數(shù)組索引從0開(kāi)始,但這里的l,r是區(qū)間表示,從1開(kāi)始考慮) int sum = queryRangeSum(dp, 2, 4); cout << "Sum of range [2, 4]: " << sum << endl; // 輸出 9 (2+3+4) return 0; }
3.二維數(shù)組求前綴和
二維數(shù)組求前綴和和一維數(shù)組求前綴和思路相似,都是通過(guò)預(yù)處理前綴和來(lái)解決此類(lèi)問(wèn)題。
類(lèi)?于?維數(shù)組的形式,如果我們能處理出來(lái)從 [0, 0] 位置到 [i, j] 位置這?區(qū)域內(nèi)所有 元素的累加和,就可以在 O(1) 的時(shí)間內(nèi),搞定矩陣內(nèi)任意區(qū)域內(nèi)所有元素的累加和。因此我們 接下來(lái)僅需完成兩步即可:
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
0 | 0 | 0 | 0 |
0 | 1 | 2 | 3 |
0 | 4 | 5 | 6 |
0 | 7 | 8 | 9 |
for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> arr[i][j];
這樣,我們填寫(xiě)前綴和矩陣數(shù)組的時(shí)候,下標(biāo)直接從 1 開(kāi)始,能?膽使? i - 1 , j - 1 位 置的值。
此時(shí)我們所求的[i,j]坐標(biāo)的和,即為下圖藍(lán)色區(qū)域位置
此時(shí)我們所求的[i,j]坐標(biāo)的和,即為下圖藍(lán)色區(qū)域位置
// 處理前綴和矩陣 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] + arr[i][j] - dp[i - 1][j - 1];
將表格抽象為四部分:分別為綠,粉,藍(lán),白
x | i | |||
0 | 0 | 0 | 0 | |
j | 0 | 1 | 2 | 3 |
0 | 4 | 5 | 6 | |
y | 0 | 7 | 8 | 9 |
如果我們想求出白色部分的和
即為:總-綠-粉-藍(lán)=白;
綠+粉=dp[i][j];
綠+藍(lán)=dp[x][y];
白=dp[i][y]-dp[x][y]-dp[i][j]+dp[x][j];
總代碼如下
#include <iostream> using namespace std; const int N = 1010; int arr[N][N]; long long dp[N][N]; int n, m, q; int main() { cin >> n >> m >> q; // 讀?數(shù)據(jù) for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> arr[i][j]; // 處理前綴和矩陣 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] + arr[i][j] - dp[i - 1][j - 1]; // 使?前綴和矩陣 int x1, y1, x2, y2; while(q--) { cin >> x1 >> y1 >> x2 >> y2; cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl; } }
4.二維矩陣中心前綴和
二維矩陣中心前綴和求取方式和二維矩陣前綴和方法類(lèi)似,不過(guò)需要多進(jìn)行處理幾步。
中心坐標(biāo)[x,y]的寬k=1中心前綴和,為以下藍(lán)色部分
x | |||
y | 1 | 2 | 3 |
4 | 5 | 6 | |
7 | 8 | 9 |
坐標(biāo)[x,y]的中心前綴和,為以下藍(lán)色部分
x | 1 | 2 | 3 | |
y | 4 | 5 | 6 | |
7 | 8 | 9 |
此時(shí)步驟為:
1.先求普通二維前綴和dp,建立首行列都為0的普通前綴和數(shù)組
x | i | |||
0 | 0 | 0 | 0 | |
j | 0 | 1 | 3 | 6 |
0 | 5 | 12 | 21 | |
y | 0 | 12 | 27 | 55 |
2.求建立新的中心前綴和數(shù)組即為(去掉為0的輔助項(xiàng)):
x1=max(0,i-k);y1=max(0,j-k);//避免出現(xiàn)越界情況
arr[i][j]=dp[x1-1][y1-1]+dp[x2][y2]-dp[x1-1][y2]-dp[x2][y2]
以下是完整代碼:
class Solution { public: vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) { int m=mat.size(),n=mat[0].size(); vector<vector<int>> dp(m+1,vector<int>(n+1)); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) { dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+mat[i-1][j-1]; } } vector<vector<int>> arr(m,vector<int>(n)); for(int i=0;i<m;i++) { for(int j=0;j<n;j++) { int x1=max(i-k,0)+1; int y1=max(j-k,0)+1; int x2=min(i+k,m-1)+1; int y2=min(j+k,n-1)+1; arr[i][j]=dp[x1-1][y1-1]+dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]; } } return arr; } };
5.前綴和與哈希表相結(jié)合
前綴和與哈希表相結(jié)合是一種非常有效的算法技巧,常用于解決數(shù)組或字符串中與子數(shù)組(或子串)和相關(guān)的問(wèn)題。這種方法的核心思想是通過(guò)前綴和來(lái)快速計(jì)算任意子數(shù)組的和,并利用哈希表來(lái)記錄這些和出現(xiàn)的頻率,從而高效地解決問(wèn)題。
1. 哈希表的作用
哈希表(Hash Table)用于記錄前綴和出現(xiàn)的頻率。在處理問(wèn)題時(shí),我們可以利用哈希表快速查找某個(gè)前綴和是否已經(jīng)出現(xiàn)過(guò),以及出現(xiàn)了多少次。
(假設(shè)需要求出i前面的等于k的子數(shù)組個(gè)數(shù))
0x1x2……i
對(duì)于i來(lái)說(shuō)數(shù)組可以分為兩段
ki的前綴和-ki
2. 前綴和與哈希表相結(jié)合的應(yīng)用
假設(shè)我們需要求出數(shù)組中所有和為k
的子數(shù)組的個(gè)數(shù)。我們可以按照以下步驟進(jìn)行:
- 初始化一個(gè)哈希表
count
,用于記錄前綴和出現(xiàn)的頻率。將count[0]
初始化為1
,表示前綴和為0
的情況(即空子數(shù)組)出現(xiàn)了1
次。 - 初始化一個(gè)變量
result
為0
,用于記錄和為k
的子數(shù)組的個(gè)數(shù)。 - 遍歷數(shù)組
arr
,計(jì)算當(dāng)前位置的前綴和prefixSum[i]
。 - 計(jì)算目標(biāo)前綴和
target = prefixSum[i] - k
。如果target
在哈希表中出現(xiàn)過(guò),說(shuō)明存在一個(gè)或多個(gè)子數(shù)組的和為k
(這些子數(shù)組的右端點(diǎn)是當(dāng)前位置i
,左端點(diǎn)可以通過(guò)哈希表中的記錄確定)。 - 將
result
增加count[target]
的值。 - 更新哈希表
count
,將prefixSum[i]
的頻率增加1
。 - 遍歷結(jié)束后,
result
就是和為k
的子數(shù)組的個(gè)數(shù)。
#include <iostream> #include <unordered_map> #include <vector> using namespace std; int numSubarraySumEqualK(vector<int>& nums, int k) { unordered_map<int, int> count; // 哈希表,記錄前綴和出現(xiàn)的頻率 count[0] = 1; // 初始化前綴和為0的頻率為1(表示空子數(shù)組) int prefixSum = 0; // 當(dāng)前位置的前綴和 int result = 0; // 和為k的子數(shù)組個(gè)數(shù) for (int num : nums) { prefixSum += num; // 計(jì)算當(dāng)前位置的前綴和 int target = prefixSum - k; // 計(jì)算目標(biāo)前綴和 if (count.find(target) != count.end()) { // 如果目標(biāo)前綴和在哈希表中出現(xiàn)過(guò),則增加結(jié)果 result += count[target]; } // 更新哈希表中當(dāng)前前綴和的頻率 count[prefixSum]++; } return result; } int main() { vector<int> nums = {1, 1, 1}; // 示例數(shù)組 int k = 2; // 目標(biāo)和 int result = numSubarraySumEqualK(nums, k); cout << "和為" << k << "的子數(shù)組個(gè)數(shù)為: " << result << endl; return 0; }
到此這篇關(guān)于C++中前綴和數(shù)組(算法)基本介紹的文章就介紹到這了,更多相關(guān)c++前綴和數(shù)組內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
C++?STL容器詳解之紅黑樹(shù)部分模擬實(shí)現(xiàn)
本文主要對(duì)紅黑樹(shù)進(jìn)行了詳細(xì)介紹,并對(duì)其核心功能進(jìn)行了模擬實(shí)現(xiàn)。文中的代碼對(duì)我們的學(xué)習(xí)或工作有一定的價(jià)值,感興趣的小伙伴可以了解一下2021-12-12淺析char 指針變量char *=p 這個(gè)語(yǔ)句的輸出問(wèn)題
下面小編就為大家?guī)?lái)一篇淺析char 指針變量char *=p 這個(gè)語(yǔ)句的輸出問(wèn)題。小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2016-05-05C++ 二叉搜索樹(shù)(BST)的實(shí)現(xiàn)方法
這篇文章主要介紹了C++ 二叉搜索樹(shù)(BST)的實(shí)現(xiàn)方法,非常不錯(cuò),具有參考借鑒價(jià)值,需要的的朋友參考下2017-04-04C語(yǔ)言函數(shù)棧幀的創(chuàng)建與銷(xiāo)毀詳解
函數(shù)棧幀(stack frame)就是函數(shù)調(diào)用過(guò)程中在程序的調(diào)用棧(call stack)所開(kāi)辟的空間,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言函數(shù)棧幀的創(chuàng)建與銷(xiāo)毀的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-09-09C語(yǔ)言深入探究自定義類(lèi)型之結(jié)構(gòu)體與枚舉及聯(lián)合
今天我們來(lái)學(xué)習(xí)一下自定義類(lèi)型,自定義類(lèi)型包括結(jié)構(gòu)體、枚舉、聯(lián)合體,小編覺(jué)得挺不錯(cuò)的,現(xiàn)在就分享給大家,也給大家做個(gè)參考2022-05-05淺析設(shè)計(jì)模式中的代理模式在C++編程中的運(yùn)用
這篇文章主要介紹了設(shè)計(jì)模式中的代理模式在C++編程中的運(yùn)用,代理模式最大的好處就是實(shí)現(xiàn)了邏輯和實(shí)現(xiàn)的徹底解耦,需要的朋友可以參考下2016-03-03