算法简介

前缀和用于快速得到数组某个连续区间内所有元素的元素和。

时间复杂度

构建前缀和数组：\(O(n)\)
求取某区间总和：\(O(1)\)

实现原理

按照如下规则构建前缀和数组：

例如：有数组 \(a\)，前缀和数组为 \(s\)。
\(s[0] = 0\)
\(s[1] = a[1]\)
\(s[2] = a[2] + a[1]\)
...
\(s[n] = a[n] + a[n-1] + a[n-2] + \cdots + a[1]\)

那么求取某一区间 [l,r] 即可用 s[r] - s[l-1] 取得

如求 \(a[3] + a[4] + a[5]\) 的和，则有：
\(s[5] = a[5] + a[4] + a[3] + a[2] + a[1]\)
\(s[2] = a[2] + a[1]\)
则有 \(a[3] + a[4] + a[5] = s[5] - s[2] = a[5] + a[4] + a[3] + a[2] + a[1] - a[2] - a[1]\)

算法实例

1. 题目描述

https://www.acwing.com/problem/content/description/797/

2. AC代码

#include <bits/stdc++.h>

const int N = 100010;

int n,m;
int sum[N],a[N];

int main() {
    std::cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) {
        std::cin >> a[i];
    }
    
    for (int i = 1; i <= n; i ++ ) {
        sum[i] = sum[i - 1] + a[i];
    }
    
    while(m -- ) {
        int l,r;
        std::cin >> l >> r;
        std::cout << sum[r] - sum[l - 1] << "\n";
    }
    
    return 0;
}

算法拓展

二维前缀和

二维前缀和就是将一维前缀和扩展到二维，快速求取某个子矩阵元素和的算法。

其中前缀和数组 sum[i,j] 表示 [1,1] 到 [i,j] 这个子矩阵的元素和。

sum[i,j] 即为红色框矩阵的和：

求解二维前缀和需要明确两个问题：

如何构造 sum 数组：
\(sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j]\)

整个外围蓝色矩形面积s[i][j] = 绿色面积s[i-1][j] + 紫色面积s[i][j-1] - 重复加的红色的面积s[i-1][j-1]+小方块的面积a[i][j];

如何求解以 [x1,y1] 为左上角坐标，[x2,y2] 为右下角坐标的子矩阵的矩阵和。
\(sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1]\)

绿色矩形的面积 = 整个外围面积s[x2, y2] - 黄色面积s[x2, y1 - 1] - 紫色面积s[x1 - 1, y2] + 重复减去的红色面积 s[x1 - 1, y1 - 1]

题目实例

https://www.acwing.com/problem/content/description/798/

AC代码

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 1010;

LL a[N][N],s[N][N];

int main()
{
    int n,m,q;
    cin >> n >> m >> q;
    
    for (int i = 1 ; i <= n ; i ++ )
        for (int j = 1 ; j <= m ; j ++ )
            cin >> a[i][j];
            
    for (int i = 1 ; i <= n ; i ++ )
        for (int j = 1 ; j <= m ; j ++ )
            s[i][j] = s[i][j-1] + s[i-1][j] - s[i-1][j-1] + a[i][j];
    
    while(q--)
    {
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] << endl;
    }
    return 0;
}