前缀和算法详解：一维与二维前缀和

前缀和算法详解

一、一维前缀和

题目描述

给定一个长度为 n 的数组，和 m 次询问；每一次询问给出两个整数 l 和 r，让我们求出区间 [l , r] 中所有数的和。

算法思路

暴力解法时间复杂度 O(m * n)，会超时。优化方案是使用前缀和数组，将查询复杂度降为 O(1)。

前缀和数组 dp[i] 表示区间 [1 , i] 中所有数的和。 状态转移方程：dp[i] = dp[i-1] + arr[i] 获取区间 [l , r] 中所有数的和：s = dp[r] - dp[l-1]

代码实现

#include <cmath>
#include <iostream>
using namespace std;
const int N = 100001;
long long dp[N];
int arr[N];
int n, m;
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        dp[i] = dp[i - 1] + arr[i];
    }
    while(m--){
        int l, r;
        cin >> l >> r;
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}

二、二维前缀和

题目描述

给定一个 n*m 的二维数组，以及 q 次查询；每一次查询给定 x1,x2,y1,y2，要求以 (x1,y1) 为左上角，(x2,y2) 为右下角的子矩阵中所有数的和。

算法思路

暴力解法时间复杂度 O(nmq)，会超时。利用二维前缀和可以将查询复杂度降为 O(1)。

设 dp[i][j] 表示以 (1,1) 为左上角，(i,j) 为右下角的子矩阵中所有数的和。 状态转移方程：dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + arr[i][j] 计算子矩阵中所有数的和：s = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]

代码实现

#include <iostream>
  std;
  N = ;
 arr[N][N];
  dp[N][N];
 n, m, q;
 x1, x2, y1, y2;
{
    cin >> n >> m >> q;
    ( i = ; i <= n; i++){
        ( j = ; j <= m; j++){
            cin >> arr[i][j];
            dp[i][j] = dp[i - ][j] + dp[i][j - ] - dp[i - ][j - ] + arr[i][j];
        }
    }
    (q--){
        cin >> x1 >> y1 >> x2 >> y2;
        cout << (dp[x2][y2] - dp[x1 - ][y2] - dp[x2][y1 - ] + dp[x1 - ][y1 - ]) << endl;
    }
     ;
}