前缀和篇——繁星斗斗数字交织中，觅得效率明月辉光（1）

前言

在这片无边无际的数字海洋中，如何从中提取出有价值的讯息，成为了计算机科学中的一项重要课题。前缀和算法，作为一种巧妙的技术，恰如其名——通过计算序列中各个元素的前缀和，能够为我们提供一种高效的查询方式，避免了重复计算的复杂度。在这篇博客中，我们将一起探索前缀和算法的奥秘，揭开它在数据处理中的应用与优势。

一. 算法简介与原理分析

1.1 原理讲解

A = [a1, a2, a3, ..., an]

那么，前缀和数组 S 就是一个满足如下关系的数组：

S[i] = A[1] + A[2] + ... + A[i]，(1 <= i <= n)

通过这个预处理步骤，我们能够将任何区间 [l, r] 内的和，通过以下公式迅速计算得到：

sum(l, r) = S[r] - S[l-1]

这一公式的妙处在于，无论查询的区间多么广泛，计算时间始终是常数级别的 O(1)，只需要在预处理阶段做 O(n) 的计算。

1.2 应用方面

• 区间求和问题： 这是前缀和算法最常见的应用。在给定一个数组时，我们常常需要求解数组中某一范围内所有元素的和。通过前缀和算法，可以将时间复杂度从 O(n) 降低到 O(1)。
• 数组的频率统计： 如果我们对数组中的某些元素出现的频率感兴趣，前缀和算法也可以轻松处理。例如，统计一个数组中，某个数值在前缀中的出现次数。
• 二维数组的区域查询： 扩展到二维数组时，前缀和算法同样表现出了强大的能力。通过二维前缀和数组，可以在常数时间内查询任意矩形区域的和。
• 字符串匹配与模式识别： 在字符串处理中，前缀和可以用来快速计算子串的哈希值，从而加速字符串匹配算法。

1.3 优劣势分析

优势：

• 时间效率高： 前缀和算法的预处理时间是 O(n)，而查询区间和的时间复杂度是 O(1)，在需要大量查询时，能显著提升效率。
• 空间效率适中： 前缀和算法的空间复杂度为 O(n)，对于大多数情况来说，这个空间开销是可以接受的。

劣势：

• 只能处理静态问题： 前缀和算法的局限性在于它仅适用于静态数组。对于动态数组（例如频繁更新的数组），前缀和需要进行复杂的重新计算，效率会大打折扣。
• 不适用于非线性数据结构： 前缀和算法主要针对一维和二维数组等线性数据结构，对于树、图等非线性数据结构的处理，前缀和的优势不明显。

1.4 改进拓展

• 差分数组： 在处理区间更新问题时，可以结合差分数组与前缀和算法，在 O(1) 时间内进行区间更新。
• 二维前缀和： 对于二维数组，前缀和算法的扩展可以帮助我们高效地查询任意矩形区域的和，常见于图像处理等领域。
• 树状数组与线段树： 在需要支持动态更新的情况下，树状数组和线段树是前缀和算法的常见替代品，能够在动态环境中提供类似的查询和更新效率。

下面我们结合具体题目进行理解运用。

二. 【模板】前缀和

2.1 题目链接：

https://www.nowcoder.com/practice/acead2f4c28c401889915da98ecdc6bf?tpId=230&tqId=2021480&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196

2.2 题目分析：

该题是典型的IO型题目（输入输出），下面我们来分析具体输入输出要求：

1. 第一行内输入两个正整数，n表示数组长度，q表示要输出的行数
2. 第二行内需要输入n个整数，即数组内的各个元素
3. 接下来需要输入q行，每一行输入两个数，分别表示计算和的起点和终点。 注意：此时的起点终点指的是第i个数，而非元素的下标！！！
4. 输出q行，每一行为该区间内元素的和

示例如图：

在这里插入图片描述

2.3 算法讲解：

暴力解法（会超时）： 该题的思路不难，可以采取每次逐个遍历该区间累加的方式进行输出，但是如此操作，会造成极大的时间和空间冗余。

前缀和： . 先预处理出来⼀个「前缀和」数组：

• ⽤ dp[i] 表⽰： [1, i] 区间内所有元素的和，那么 dp[i - 1] ⾥⾯存的就是 [1, i - 1] 区间内所有元素的和，那么：可得递推公式： dp[i] = dp[i - 1] + arr[i] ；
• 使⽤前缀和数组，「快速」求出「某⼀个区间内」所有元素的和：当询问的区间是 [l, r] 时：区间内所有元素的和为： dp[r] - dp[l - 1] 。

2.4 代码实现

#include <iostream>

using namespace std;
const int N=100010;
long long nums[N], sums[N];
int main() {
    int n,p;
    cin>>n>>p;//输入
    
    for(int i=1;i<=n;i++)
    {
        cin>>nums[i];
    }//输入各个元素
    for(int i=1;i<=n;i++)
    {
        sums[i]=sums[i-1]+nums[i];

    }//计算前缀和
    while(p--)
    {
        int l,r;
        cin>>l>>r;
        cout<<sums[r]-sums[l-1]<<endl;
    }
    return 0;

}
// 64 位输出请用 printf("%lld")

三. 【模板】二维前缀和

3.1 题目链接：

https://www.nowcoder.com/practice/99eb8040d116414ea3296467ce81cbbc?tpId=230&tqId=2023819&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196

3.2 题目分析：

本题为IO型，我们先来具体分析输入输出要求：

1. 本题存在一个nxm的矩阵，且下标从1开始
2. 第一行输入三个整数n,m,q,其中n和m表示矩阵规格，q则表示需要做q行输出
3. 之后输入q行下标，分别为x1,y1,x2,y2，求取以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和 注意：此处下标的顺序切勿混淆！！！
4. 输出q行上述和

3.3 思路讲解：

以此图为例，以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和即为D所表示的区域。

在这里插入图片描述

类⽐于⼀维数组的形式，如果我们能处理出来从 [0, 0] 位置到 [i, j] 位置这⽚区域内所有 元素的累加和，就可以在 O(1) 的时间内，搞定矩阵内任意区域内所有元素的累加和。因此我们 接下来仅需完成两步即可：

• 第⼀步：构建前缀和矩阵 这⾥就要⽤到⼀维数组⾥⾯的拓展知识，我们要在矩阵的最上⾯和最左边添加上⼀⾏和⼀列 0，这样我们就可以省去⾮常多的边界条件的处理（可以⾃⾏尝试直接搞出来前缀和矩 阵，边界条件的处理会令人崩溃）。处理后的矩阵就像这样：

在这里插入图片描述

这样，我们填写前缀和矩阵数组的时候，下标直接从 1 开始，能⼤胆使⽤ i - 1 , j - 1 位 置的值。 注意 dp 表与原数组 matrix 内的元素的映射关系： i. 从 dp 表到 matrix 矩阵，横纵坐标减⼀； ii. 从 matrix 矩阵到 dp 表，横纵坐标加⼀。

前缀和矩阵中 sum[i][j] 的含义，以及如何递推⼆维前缀和⽅程： a. sum[i][j] 的含义：

在这里插入图片描述

下面我们逐个分析这四个区域：

• 黄色：即矩阵martix[i-1][j-1]，注意映射关系
• 红色：可直接求出，即sum[i-1][j-1]
• 蓝色：不好直接求出，但是红+蓝=sum[i-1][j]，蓝色只需令和再减去红色即可
• 绿色：原理同上，红+绿=sum[i][j-1]

• 第⼆步：使⽤前缀和矩阵 题⽬的接⼝中提供的参数是原始矩阵的下标，为了避免下标映射错误，这⾥直接先把下标映射成 dp 表⾥⾯对应的下标： row1++, col1++, row2++, col2++

接下来分析如何使⽤这个前缀和矩阵，如下图（注意这⾥的 row 和 col 都处理过了，对应的正 是 sum 矩阵中的下标）：

在这里插入图片描述

对于左上⻆ (row1, col1) 、右下⻆ (row2, col2) 围成的区域，正好是红⾊的部分。因 此我们要求的就是红⾊部分的⾯积，继续分析⼏个区域： i. ⻩⾊，能直接求出来，就是 sum[row1 - 1, col1 - 1] （为什么减⼀？因为要剔除 掉 row 这⼀⾏和 col 这⼀列） ii. 绿⾊，直接求不好求，但是和⻩⾊拼起来，正好是 sum 表内 sum[row1 - 1][col2] 的数据； iii. 同理，蓝⾊不好求，但是 蓝 + ⻩ = sum[row2][col1 - 1] ； iv. 再看看整个⾯积，好求嘛？⾮常好求，正好是 sum[row2][col2] ； v. 那么，红⾊就 = 整个⾯积 - ⻩ - 绿 - 蓝，但是绿蓝不好求，我们可以这样减：整个⾯积 -（绿

• ⻩ ）-（蓝 + ⻩），这样相当于多减去了⼀个⻩，再加上即可 综上所述：红 = 整个⾯积 - （绿 + ⻩）- （蓝 + ⻩）+ ⻩，从⽽可得红⾊区域内的元素总和为：

3.4 代码实现：

#include <iostream>
using namespace std;
const int N=1010;
int arr[N][N];
long long dp[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>>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];
        }
    }
    //使用前缀和数组
    while(q--)
    {
        int x1,y1,x2,y2;
        cin>>x1>>y1>>x2>>y2;
        cout<<dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]<<endl;

    }//输出数据
    return 0;
}
// 64 位输出请用 printf("%lld")

小结

本篇关于前缀和的介绍讲解较为基础，将于后续文章中结合进阶难度的题目循序渐进，希望能对大家的学习产生帮助，欢迎各位佬前来支持斧正！！！