算法基础之前缀和

前缀和

• 唯一用处 : 求l-r区间的数组和

  • 遍历一边 复杂度On
  • 用前缀和数组 复杂福O1

•   #include<iostream>
    using namespace std;
    const int N=100010;
    int a[N],s[N];  //一个数组放元素 另一个放前缀和
    int n,m;
    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++) scanf("%d", &a[i]);
        
        //s[0]=0 全局变量默认 求前缀
        for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
        
        while(m--){
            int l,r;
            scanf("%d%d", &l, &r);
            
            //算l,r 区间的前缀和 即s[r] - s[l - 1]
            printf("%d\n", s[ r ]-s[l - 1]);
        
        }
        
        return 0;
    }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23