C++ 前缀和数组

一.  一维数组前缀和

 1.1. 定义

       前缀和算法通过预处理数组，计算从起始位置到每个位置的和，生成一个新的数组（前缀和数组）。利用该数组，可以快速计算任意区间的和，快速求出数组中某一段连续区间的和。

 

1.2. 公式

1.2.1. 前缀和数组公式

 

prefix[i] 表示的是从数组 nums 的第 0 个元素到第 i - 1 个元素的所有元素之和，也就是前缀和。

prefix[i - 1] 是从第 0 个元素到第 i - 2 个元素的和，

nums[i - 1] 是数组 nums 中第 i - 1 个元素的值。

        所以这个公式的意思是：当前位置的前缀和等于前一个位置的前缀和加上当前位置对应的数组元素的值。

 

假设有一个数组 nums = [1, 2, 3, 4, 5]，我们来计算它的前缀和数组。

初始化 prefix[0] = 0（通常会把前缀和数组的第 0 个元素初始化为 0，方便后续计算）。

当 i = 1 时，prefix[1] = prefix[0] + nums[0] = 0 + 1 = 1。

当 i = 2 时，prefix[2] = prefix[1] + nums[1] = 1 + 2 = 3。

当 i = 3 时，prefix[3] = prefix[2] + nums[2] = 3 + 3 = 6。

当 i = 4 时，prefix[4] = prefix[3] + nums[3] = 6 + 4 = 10。

当 i = 5 时，prefix[5] = prefix[4] + nums[4] = 10 + 5 = 15。

 

代码实现：

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1005; //默认数组最大存储空间 

int nums[MAXN]; //实际存储数据的数组,初始化元素值为0

int prefix[MAXN]={0}; //前缀和数组,初始化元素值为0 

int n; //数组实际大小 

int main() {

        cin>>n; //输入数组的大小

        //循环输入数组中的每个元素的值

        for(int i=0;i<n;i++) cin>>nums[i];

        cout<<"输出原数组的值:" ;

        for(int i=0;i<n;i++) cout<<nums[i]<<" "; 

        //构建前缀和数组

        for(int i=1;i<=n;i++){

        prefix[i]=prefix[i-1]+nums[i-1];

 } 

 cout<<"\n输出前缀和的值:" ;

//循环输出前缀和数组中存储的值

for(int i=1;i<=n;i++){

        cout<<prefix[i]<<" ";

 } 

return 0;

}

 

1.2.2、区间和数组公式

sum(i, j) 表示的是数组 nums 中从第 i 个元素到第 j 个元素的所有元素之和。prefix[j + 1] 是从第 0 个元素到第 j 个元素的和。

prefix[i] 是从第 0 个元素到第 i - 1 个元素的和。

那么用 prefix[j + 1] 减去 prefix[i] 就得到了从第 i 个元素到第 j 个元素的和。

还是使用上面的数组 nums = [1, 2, 3, 4, 5]，假设我们要计算从第 1 个元素（索引为 0）到第 3 个元素（索引为 2）的和，即 sum(0, 2)。

我们已经计算出前缀和数组 prefix = [0, 1, 3, 6, 10, 15]。

根据公式 sum(0, 2) = prefix[2 + 1] - prefix[0] 

                     = prefix[3] - prefix[0] 

                     = 6 - 0 

                     = 6

 

代码实现：

#include <bits/stdc++.h>

using namespace std;

const int MAXN=1005; //默认数组最大存储空间 

int nums[MAXN]; //实际存储数据的数组,初始化元素值为0

int prefix[MAXN]={0}; //前缀和数组,初始化元素值为0 

int n,l,r; //数组实际大小 l代表起始位置、r代表结束位置 

int main() {

        cin>>n; //输入数组的大小

       //循环输入数组中的每个元素的值

       for(int i=0;i<n;i++) cin>>nums[i];

       cout<<"输出原数组的值:" ;

       for(int i=0;i<n;i++) cout<<nums[i]<<" "; 

       for(int i=1;i<=n;i++){ //构建前缀和数组

               prefix[i]=prefix[i-1]+nums[i-1];

        } 

       cout<<"\n输出前缀和的值:" ;

       for(int i=1;i<=n;i++){//循环输出前缀和数组中存储的值

        cout<<prefix[i]<<" ";

 } 

 cin>>l>>r; //输入计算区间的起始位置

 cout<<prefix[r+1]-prefix[l];

 return 0;

}

 

1.2.3、动态规划思想

        这里的 dp 通常是动态规划数组，dp[i] 表示的是与数组 arr 前 i 个元素相关的某种状态值。这个公式表示当前状态 dp[i] 可以由前一个状态 dp[i - 1] 加上当前数组元素 arr[i] 得到。

        假设我们要计算数组 arr = [1, 2, 3, 4, 5] 中每个位置的累积和，就可以使用这个动态规划的思想。

初始化 dp[0] = arr[0]。

当 i = 1 时，dp[1] = dp[0] + arr[1] = 1 + 2 = 3。

当 i = 2 时，dp[2] = dp[1] + arr[2] = 3 + 3 = 6。

当 i = 3 时，dp[3] = dp[2] + arr[3] = 6 + 4 = 10。

当 i = 4 时，dp[4] = dp[3] + arr[4] = 10 + 5 = 15。

 

1.3、适用题目

区间和查询：如求子数组和。

频率统计：如统计满足条件的子数组数量。

优化时间复杂度：将区间和查询从O(n)降至O(1)。

 

1.4、优缺点
1、优点

高效查询：区间和查询时间复杂度为O(1)。

预处理简单：前缀和数组的构建时间复杂度为O(n)。

2、缺点

空间开销：需要额外O(n)空间存储前缀和数组。

仅适用于静态数组：数组元素不变时适用，频繁更新时不适用。

 

二.  二维数组前缀和

2.1、定义

        二维数组前缀和是一种用于高效处理二维数组区域和查询的数据结构和算法。

        对于一个二维数组arr，其前缀和数组prefix中prefix[i][j]表示从arr[0][0]到arr[i][j]这个矩形区域内所有元素的和。

 

2.2、公式

        构建二维数组前缀和的核心思想是利用动态规划的思想，通过已知的前缀和来计算新的前缀和。

 

2.3、区域和查询

如果我们想查询从 (x1, y1) 到 (x2, y2) 这个矩形区域内所有元素的和，可以使用以下公式：

sum=prefix[x2][y2]−prefix[x1−1][y2]−prefix[x2][y1−1]+prefix[x1−1][y1−1]

        这个公式的含义是：整个大矩形的前缀和减去上方小矩形的前缀和和左方小矩形的前缀和，再加上左上方小矩形的前缀和（因为这个区域被多减了一次）。

 

2.4、代码实现

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1005; // 默认二维数组最大行数和列数

int nums[MAXN][MAXN] = {0}; // 实际存储二维数据的数组，初始化元素值为 0

int prefix[MAXN][MAXN] = {0}; // 二维前缀和数组，初始化元素值为 0 

int n, m, q; // n 二维数组实际行数、m 二维数组实际列数、q 查询区间的次数

int x,y,x2,y2; // x,y 代表查询区间的左上角坐标，x2,y2 代表查询区间的右下角坐标

 

代码实现：

int main() {

        cin >> n >> m >> q; // 输入二维数组的行数、列数和查询次数

        // 循环输入二维数组中的每个元素的值

        for (int i = 1; i <= n; i++) {

                for (int j = 1; j <= m; j++) {

                cin >> nums[i][j];

         }

}

 // 构建二维前缀和数组

 for (int i = 1; i <= n; i++) {

         for (int j = 1; j <= m; j++) {

         prefix[i][j] = prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1] + nums[i][j];

         }

}

while (q--) {

         cin >> x >> y >> x2 >> y2; // 输入查询区间的左上角和右下角坐标

        // 计算并输出查询区间的和

        cout << prefix[x2][y2] - prefix[x - 1][y2] - prefix[x2][y - 1] + prefix[x - 1][y - 1] << endl;

    }

    return 0;

}