【算法】基础算法004之前缀和

👀樊梓慕：个人主页

 🎥个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子，都是对生命的辜负

前言

本篇文章为大家带来前缀和算法，前缀和算法可以以O(1)的时间复杂度快速求出某一段连续区间的和，这个连续区域既可以是一维的也可以是二维的。

欢迎大家📂收藏📂以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。 

=========================================================================

GITEE相关代码：🌟樊飞 (fanfei_c) - Gitee.com🌟

=========================================================================

1.⼀维前缀和

【模板】前缀和_牛客题霸_牛客网 (nowcoder.com)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

 前缀和：可以快速求出某一段连续区间的和。

本道题目如果使用暴力计算的话会超时，所以需要进行优化。

前缀和解题模板

1. 第一步：预处理出来一个前缀和数组，比如本题dp[i]表示1-i区间内所有元素的和，且dp[i]=dp[i-1]+arr[i]；
2. 第二步：使用前缀和数组，比如本题求[l,r]区间元素的和就是dp[r]-dp[l-1]；

#include 
#include 
using namespace std;
int main() {
    // 1.输入数据
    int n,q;
    cin>>n>>q;
    vector arr(n+1);
    for(int i=1;i>arr[i];
    // 2.预处理出来一个前缀和数组
    vector dp(n+1);
    for(int i=1;i>l>>r;
        coutm>>q;
    vector arr(n+1,vector(m+1));
    for(int i=1;iarr[i][j];
    // 2.预处理前缀和矩阵
    vector dp(n+1,vector(m+1));
    for(int i=1;ix1>>y1>>x2>>y2;
        cout