当前位置：首页 > article >正文

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

article 2024/12/3 8:39:00

在这里插入图片描述

前言

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

一. 算法简介与原理分析

1.1 原理讲解

前缀和算法的核心思想是：***对于一个数组，预先计算出数组从第一个元素到当前元素的累积和。这种累积和的结果，能够帮助我们快速计算出数组任意区间内的和。** 举个简单的例子，假设有一个数组 A，其元素为：

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型题目（输入输出），下面我们来分析具体输入输出要求：

第一行内输入两个正整数，n表示数组长度，q表示要输出的行数
第二行内需要输入n个整数，即数组内的各个元素
接下来需要输入q行，每一行输入两个数，分别表示计算和的起点和终点。
注意：此时的起点终点指的是第i个数，而非元素的下标！！！
输出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型，我们先来具体分析输入输出要求：

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

sum[i][j] 表⽰，从 [0, 0] 位置到 [i, j] 位置这段区域内，所有元素的累加和，即下图红黄绿蓝四个区域相加之和。

在这里插入图片描述
下面我们逐个分析这四个区域：

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

综上,sum[i][j]=红+绿+红+蓝+黄-红=sum[i][j-1]+sum[i-1][j]+martix[i-1][j-1]-sum[i-1][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. 那么，红⾊就 = 整个⾯积 - ⻩ - 绿 - 蓝，但是绿蓝不好求，我们可以这样减：整个⾯积 -（绿

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

sum[row2][col2]-sum[row2][col1 - 1]-sum[row1 - 1][col2]+sum[row1 - 1][col1 - 1]

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")