前缀和与差分

洛谷：3372
OJ平台：3372

前缀和定义

前缀和是指某序列的前n项和，可以把它理解为数学上的数列的前n项和。

原数组：a={1, 3, 5, 7, 9}
前缀和：prefixSum={1, 4, 9, 16, 25} 前缀和就是第i项是原数组前i项之和
prefixsum[0]=a[0]=1
prefixsum[1]=a[0]+a[1]=4
prefixsum[2]=a[0]+a[1]+a{2}=9
prefixsum[3]=a[0]+a[1]+a{2}+a[3]=16
prefixsum[4]=a[0]+a[1]+a{2}+a[3]+a[4]=25

前缀和是一种预处理，当多次查询子数组的和时，能大大降低查询的时间复杂度。

二、问题

输入一个长度为n的整数序列。接下来再输入m个询问，每个询问输入一对L, R。对于每个询问，输出原序列中从第L个数到第R个数的和。

例如：有5个元素的数组，有3次询问区间和
5 3
2 4 8 6 9
0 2
1 3
2 4
结果为：
14 (2+4+8)
18(4+8+6)
23(8+6+9)

三、求区间和暴力解法

/**************************************************************** 
 * Description:   暴力求前缀和， 时间复杂度 O(n*m)
 * Author: Alex Li
 * Date: 2023-11-09 17:11:12
 * LastEditTime: 2023-11-09 18:27:42
****************************************************************/
#include <iostream>
using namespace std;

int main(){
    int n, m;
    cin>>n>>m;
    int a[n];
    
  
    for (int i = 0; i <n; i++){
        cin>>a[i];
    }

    while(m--){
        int l,r;
        int sum=0;
        cin>>l>>r;
        for (int i = l; i <=r;i++){
            sum+=a[i];
        }
        cout<<sum<<'\n';
    }
    
}

四、前缀和求区间值

暴力算法的时间复杂度为O(n*m)，如果n和m的数据量稍微大一点就有可能超时，而我们如果使用前缀和的方法来做的话就能够将时间复杂度降到O(n+m),大大提高了运算效率。

/**************************************************************** 
 * Description:   利用数组求前缀和， 时间复杂度 O(n+m)
 * Author: Alex Li
 * Date: 2023-11-09 17:11:12
 * LastEditTime: 2023-11-09 18:48:15
****************************************************************/
#include <iostream>
using namespace std;

int main(){
    int n, m;
     cin>>n>>m;
    int a[n],sum[n];
    
   cin>>a[0];
   sum[0]=a[0];

    for (int i = 1; i <n; i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }

    while(m--){
        int l,r;
        cin>>l>>r;
        if(l!=0)cout<<sum[r]-sum[l-1]<<'\n';
           else cout<<sum[r]<<'\n';
    }
    
}

五、二维求区间和

输入一个n行m列的整数矩阵，再输入q个询问，每个询问包含四个整数x1, y1, x2, y2，表示一个子矩阵的左上角坐标和右下角坐标。对于每个询问输出子矩阵中所有数的和。

B3693

差分

差分数组是用来表示一个数组中每个元素之间的变化量的数组。假设有一个原始数组 a[]，对应的差分数组 b[] 的定义为：b[i]=a[i]−a[i−1](i≥1)，其中 b[1]=a[1]，表示原始数组的第一个元素。

优点：差分数组允许对一个区间的修改转化为对两个端点的操作。
使用场景：常用于需要频繁对某些区间进行相同增量操作的问题。

原数组：a[1, 4, 3, 5, 2]
差分数组： b[1, 3, -1, 2, -3]
差分数组的前缀和数组就是原数组。
当在原数组需要在某区间同时加减某数时，可以直接利用差分数组。
比如在原数组2-4的元素都加上3.
原数组变为a[1,7, 6, 8, 2]
差分数组只需要修改b[2]+3, b[5]-3，b[1, 6, -1, 2, -6]
如果原数组在i~j 之间加k , 差分数组只要修改b[i]+k, b[j+1]-k 即可

例题：

题目描述：

给定一个长度为N的序列，进行A次操作，每次操作在Li和Ri这个区间加上一个数Ci，然后有B次询问Li到Ri的区间和，初始序列都是0。
输入格式：
第一行三个整数N、A、B。
接下来A行，每行三个数Li、Ri、Ci 1<=Li,Ri,Ci<=N
接下来B行，每行两个数Li、Ri 范围同上
输出格式：
对于每次询问，输出一行一个整数

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

前缀和与差分