【专题四】前缀和（1）：前缀和重要思想及方法

📝前言说明：

• 本专栏主要记录本人的基础算法学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

DP34 【模板】前缀和

这道题是牛客的。

一维数组

这道题解刨一下前缀和题型的重要思想。

暴力解法：
每次询问都遍历整个数组，找到第l个位置，然后从第l个位置开始往后+r个数，时间复杂度：O(q * n)

前缀和方法：用于快速求出数组中某一个连续区间的和
让每次询问，求和的时间复杂度降到O(1)
本质上是一种空间换时间的思想。

具体步骤分两步：

• 第一步：预处理一个前缀和数组dp
• 第二步：使用前缀和数组

具体如何做，请看下图

但是，这里还有一个边界问题：就是当从位置0开始的时候，dp[-1]会越界。
我们只需要在初始化的时候让数组多开一个空间，即让dp[0] == 0即可，（类似于链表的哨兵节点）

具体解题代码：

#include <iostream>
using namespace std;

int main() 
{
    int n, q;
    cin >> n >> q;
    long long arr[n + 1], dp[n + 1];
    arr[0] = 0; dp[0] = 0; 
    for(int i = 1; i <= n; i++) cin >> arr[i];
    // 预处理前缀和数组
    for(int i = 1; i <= n; i++) dp[i] = dp[i - 1] + arr[i];
    while(q--)
    {
        int l, r;
        cin >> l >> r;
        // 计算区间和
        cout << dp[r] - dp[l - 1] << endl;
    }
    return 0;
}

时间复杂度：O(n + q) ：
空间复杂度：O(n)

DP35 【模板】二维前缀和

这道题也是牛客的。

二维数组

二维情况下的前缀和数组。

同样，我们先分析暴力求解的方法：
对于每个询问，找到左上的位置然后一直遍历到右下的位置，并在这个过程中将元素相加。
最坏的时间复杂度就是：O($n^2$ * q) ：每次都从[1, 1]到[n, n]

更好的做法：利用前缀和数组（空间换时间），使用前缀和数组的关键点有两个：

• 前缀和数组中，每一个位置代表的意义
• 初始化前缀和数组的时间复杂度要尽可能的小，即：利用已有格子的信息

本题针对以上两点：

• dp[i][j]：从[1, 1]到[i, j]位置，这个矩阵的所有元素和
• 求dp[i][j]：利用面积 - 面积

具体分析如下：

本题具体代码：

#include <iostream>
#include<vector>
using namespace std;

int main() 
{
    long n, m, q;
    cin >> n >> m >> q;
    vector<vector<long long>> arr(n + 1, vector<long long>(m + 1, 0));
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            cin >> arr[i][j];
        }
    }
    vector<vector<long long>> dp(n + 1, vector<long long>(m + 1, 0));
    // 初始化前缀和数组
    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] - dp[i - 1][j - 1] + arr[i][j];
        }
    }
    while(q--)
    {
        int x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << endl;
    }
}

时间复杂度：O(n * m + q) ：
空间复杂度：O(n * m)

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！