Next Topic

前缀和与差分

数据结构与算法第六章查找前缀和与差分

一、定义

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

原数组：1 3 5 7 9
前缀和：1 4 9 16 25 前缀和就是第i项是原数组前i项之和
差分：1 2 2 2 2 差分就是第i项等于原数组第i项减去第i-1项

差分与前缀和可以看成是逆运算。

二、问题

输入一个长度为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

Previous Topic

Back to Lesson

Next Topic