欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++中前綴和數(shù)組(算法)基本介紹

 更新時間:2024年12月13日 11:54:07   作者:貓咪-9527  
前綴和(Prefix Sum)是指數(shù)組中某個位置之前的所有元素的和,本文將介紹C++中前綴和數(shù)組(算法)基本概念,感興趣的朋友一起看看吧

1.前言

如何快速求得一個數(shù)組的前綴和?

1. 1 前綴和的基本概念

前綴和(Prefix Sum)是指數(shù)組中某個位置之前的所有元素的和。對于數(shù)組arr,其前綴和數(shù)組prefixSum定義為:

  • prefixSum[0] = 0prefixSum[i] = prefixSum[i-1] + arr[i-1](對于i > 0
  • 這樣,任意子數(shù)組arr[l...r]的和可以通過prefixSum[r+1] - prefixSum[l]快速計算出來。

2.一維數(shù)組的前綴和

在處理數(shù)組區(qū)間和問題時,前綴和(Prefix Sum)是一個非常有效的工具,可以大大加快查詢速度。下面詳細解釋如何預(yù)處理前綴和數(shù)組,并使用前綴和數(shù)組快速計算任意區(qū)間的元素和。

步驟一:預(yù)處理前綴和數(shù)組

給定一個數(shù)組arr,長度為n,我們可以預(yù)處理一個前綴和數(shù)組dp,其中dp[i]表示數(shù)組arr從索引1到索引i的所有元素的和。

初始化dp[0] = 0(這是為了方便計算從索引1開始的區(qū)間和)。

使用遞推公式dp[i] = dp[i - 1] + arr[i - 1]來計算dp數(shù)組的每個元素。注意,這里arr的索引從0開始,而dp的索引

1開始模擬區(qū)間[1, i]//從1開始是為了避免從0開始時會出現(xiàn)-1,從而進行判斷,減少復(fù)雜邊界情況

  • 12345
012345

!!!此步是為了處理邊界情況

具體代碼如下:

std::vector<int> dpsum(const vector<int>& arr) {
    int n = arr.size();
    vector<int> dp(n + 1, 0); // dp 數(shù)組的長度是 n+1,并初始化為 0
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1] + arr[i - 1];
    }
    return dp;
}

步驟二:使用前綴和數(shù)組快速計算區(qū)間和

給定一個區(qū)間[l, r],我們可以利用預(yù)處理好的前綴和數(shù)組dp快速計算區(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];
}

下面展示一個一維數(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ù)組的長度是 n+1,并初始化為 0
    for (int i = 1; i <= n; ++i) {
        dp[i] = dp[i - 1] + arr[i - 1];
    }
    return dp;
}
// 查詢區(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);
    // 查詢區(qū)間 [2, 4] 的和(注意C++中數(shù)組索引從0開始,但這里的l,r是區(qū)間表示,從1開始考慮)
    int sum = queryRangeSum(dp, 2, 4);
    cout << "Sum of range [2, 4]: " << sum << endl; // 輸出 9 (2+3+4)
    return 0;
}

3.二維數(shù)組求前綴和

二維數(shù)組求前綴和和一維數(shù)組求前綴和思路相似,都是通過預(yù)處理前綴和來解決此類問題。

類?于?維數(shù)組的形式,如果我們能處理出來從 [0, 0] 位置到 [i, j] 位置這?區(qū)域內(nèi)所有 元素的累加和,就可以在 O(1) 的時間內(nèi),搞定矩陣內(nèi)任意區(qū)域內(nèi)所有元素的累加和。因此我們 接下來僅需完成兩步即可:

123
456
789
0000
0123
0456
0789
for(int i = 1; i <= n; i++) 
 for(int j = 1; j <= m; j++)
 cin >> arr[i][j];

這樣,我們填寫前綴和矩陣數(shù)組的時候,下標直接從 1 開始,能?膽使? i - 1 , j - 1 位 置的值。

此時我們所求的[i,j]坐標的和,即為下圖藍色區(qū)域位置

96284d6e93814b7594510c6a56b421fe.png

此時我們所求的[i,j]坐標的和,即為下圖藍色區(qū)域位置

58ac883bdd4f4c1ea216117335597e87.png

 // 處理前綴和矩陣
 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];

將表格抽象為四部分:分別為綠,粉,藍,白

x

i

0

0

0

0

j

0

1

2

3

0

4

5

6

y

0

7

8

9

如果我們想求出白色部分的和

即為:總-綠-粉-藍=白;

綠+粉=dp[i][j];

綠+藍=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.二維矩陣中心前綴和

二維矩陣中心前綴和求取方式和二維矩陣前綴和方法類似,不過需要多進行處理幾步。

中心坐標[x,y]的寬k=1中心前綴和,為以下藍色部分

x

y

1

2

3

4

5

6

7

8

9

坐標[x,y]的中心前綴和,為以下藍色部分

x

1

2

3

y

4

5

6

7

8

9

此時步驟為:

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的輔助項):

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)的問題。這種方法的核心思想是通過前綴和來快速計算任意子數(shù)組的和,并利用哈希表來記錄這些和出現(xiàn)的頻率,從而高效地解決問題。

1. 哈希表的作用

哈希表(Hash Table)用于記錄前綴和出現(xiàn)的頻率。在處理問題時,我們可以利用哈希表快速查找某個前綴和是否已經(jīng)出現(xiàn)過,以及出現(xiàn)了多少次。

(假設(shè)需要求出i前面的等于k的子數(shù)組個數(shù))

0x1x2……i

對于i來說數(shù)組可以分為兩段

ki的前綴和-ki

2. 前綴和與哈希表相結(jié)合的應(yīng)用

假設(shè)我們需要求出數(shù)組中所有和為k的子數(shù)組的個數(shù)。我們可以按照以下步驟進行:

  • 初始化一個哈希表count,用于記錄前綴和出現(xiàn)的頻率。將count[0]初始化為1,表示前綴和為0的情況(即空子數(shù)組)出現(xiàn)了1次。
  • 初始化一個變量result0,用于記錄和為k的子數(shù)組的個數(shù)。
  • 遍歷數(shù)組arr,計算當(dāng)前位置的前綴和prefixSum[i]
  • 計算目標前綴和target = prefixSum[i] - k。如果target在哈希表中出現(xiàn)過,說明存在一個或多個子數(shù)組的和為k(這些子數(shù)組的右端點是當(dāng)前位置i,左端點可以通過哈希表中的記錄確定)。
  • result增加count[target]的值。
  • 更新哈希表count,將prefixSum[i]的頻率增加1
  • 遍歷結(jié)束后,result就是和為k的子數(shù)組的個數(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ù)組個數(shù)
    for (int num : nums) {
        prefixSum += num; // 計算當(dāng)前位置的前綴和
        int target = prefixSum - k; // 計算目標前綴和
        if (count.find(target) != count.end()) {
            // 如果目標前綴和在哈希表中出現(xiàn)過,則增加結(jié)果
            result += count[target];
        }
        // 更新哈希表中當(dāng)前前綴和的頻率
        count[prefixSum]++;
    }
    return result;
}
int main() {
    vector<int> nums = {1, 1, 1}; // 示例數(shù)組
    int k = 2; // 目標和
    int result = numSubarraySumEqualK(nums, k);
    cout << "和為" << k << "的子數(shù)組個數(shù)為: " << result << endl;
    return 0;
}

到此這篇關(guān)于C++中前綴和數(shù)組(算法)基本介紹的文章就介紹到這了,更多相關(guān)c++前綴和數(shù)組內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Qt中QUndoView控件的具體使用

    Qt中QUndoView控件的具體使用

    QUndoView是Qt框架中用于可視化顯示QUndoStack內(nèi)容的控件,本文主要介紹了Qt中QUndoView控件的具體使用,具有一定的參考價值,感興趣的可以了解一下
    2025-04-04
  • 如何利用Matlab繪制出好看的火山圖

    如何利用Matlab繪制出好看的火山圖

    火山圖是散點圖的一種,它將統(tǒng)計測試中的統(tǒng)計顯著性量度和變化幅度相結(jié)合,從而能夠幫助快速直觀地識別那些變化幅度較大且具有統(tǒng)計學(xué)意義的數(shù)據(jù)點。本文將通過Matlab繪制好看的火山圖,需要的可以參考一下
    2022-03-03
  • C++?STL容器詳解之紅黑樹部分模擬實現(xiàn)

    C++?STL容器詳解之紅黑樹部分模擬實現(xiàn)

    本文主要對紅黑樹進行了詳細介紹,并對其核心功能進行了模擬實現(xiàn)。文中的代碼對我們的學(xué)習(xí)或工作有一定的價值,感興趣的小伙伴可以了解一下
    2021-12-12
  • Qt獲取git版本信息的具體方法

    Qt獲取git版本信息的具體方法

    這篇文章主要介紹了Qt獲取git版本信息的具體方法,今天又碰到這個問題了,想根據(jù)具體的git版本信息做代碼問題確認,文中有詳細的解決方案,具有一定的參考價值,需要的朋友可以參考下
    2024-04-04
  • 淺析char 指針變量char *=p 這個語句的輸出問題

    淺析char 指針變量char *=p 這個語句的輸出問題

    下面小編就為大家?guī)硪黄獪\析char 指針變量char *=p 這個語句的輸出問題。小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-05-05
  • C++ 二叉搜索樹(BST)的實現(xiàn)方法

    C++ 二叉搜索樹(BST)的實現(xiàn)方法

    這篇文章主要介紹了C++ 二叉搜索樹(BST)的實現(xiàn)方法,非常不錯,具有參考借鑒價值,需要的的朋友參考下
    2017-04-04
  • C++三體星戰(zhàn)小游戲源代碼

    C++三體星戰(zhàn)小游戲源代碼

    這篇文章主要給大家介紹了關(guān)于C++三體星戰(zhàn)小游戲的相關(guān)資料,文中給出了詳細完整的代碼示例,對大家的學(xué)習(xí)或者工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2023-08-08
  • C語言函數(shù)棧幀的創(chuàng)建與銷毀詳解

    C語言函數(shù)棧幀的創(chuàng)建與銷毀詳解

    函數(shù)棧幀(stack frame)就是函數(shù)調(diào)用過程中在程序的調(diào)用棧(call stack)所開辟的空間,下面這篇文章主要給大家介紹了關(guān)于C語言函數(shù)棧幀的創(chuàng)建與銷毀的相關(guān)資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下
    2022-09-09
  • C語言深入探究自定義類型之結(jié)構(gòu)體與枚舉及聯(lián)合

    C語言深入探究自定義類型之結(jié)構(gòu)體與枚舉及聯(lián)合

    今天我們來學(xué)習(xí)一下自定義類型,自定義類型包括結(jié)構(gòu)體、枚舉、聯(lián)合體,小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考
    2022-05-05
  • 淺析設(shè)計模式中的代理模式在C++編程中的運用

    淺析設(shè)計模式中的代理模式在C++編程中的運用

    這篇文章主要介紹了設(shè)計模式中的代理模式在C++編程中的運用,代理模式最大的好處就是實現(xiàn)了邏輯和實現(xiàn)的徹底解耦,需要的朋友可以參考下
    2016-03-03

最新評論