前缀和
具体做法:首先做一个预处理,定义一个sum[]数组,sum[i]代表a数组中前i个数的和。
求前缀和运算:
const int N=1e5+10; int sum[N],a[N]; //sum[i]=a[1]+a[2]+a[3].....a[i]; for(int i=1;i<=n;i++) { sum[i]=sum[i-1]+a[i]; } //然后查询操作: scanf("%d%d",&l,&r); printf("%d\n", sum[r]-sum[l-1]);对于每次查询,只需执行sum[r]-sum[l-1] ,时间复杂度为O(1)
原理
sum[r] =a[1]+a[2]+a[3]+a[l-1]+a[l]+a[l+1]......a[r]; sum[l-1]=a[1]+a[2]+a[3]+a[l-1]; sum[r]-sum[l-1]=a[l]+a[l+1]+......+a[r];
图解
这样,对于每个询问,只需要执行 sum[r]-sum[l-1]。输出原序列中从第l个数到第r个数的和的时间复杂度变成了O(1)。
我们把它叫做一维前缀和。
总结:
最后上代码~
/* 简单前缀和 用前缀和的时候记得原本数组从1开始 那么l~r区间的和就是sum[r]-sum[l-1]; */ #include<bits/stdc++.h> using namespace std; #define int long long const int maxn=1e5+10; int a[maxn]; int sum[maxn]; signed main() { int n,m,i,j,l,r; cin>>n>>m; for(i=1;i<=n;i++){ cin>>a[i]; } sum[0]=0; for(i=1;i<=n;i++){ sum[i]=sum[i-1]+a[i]; } while(m--){ cin>>l>>r; cout<<sum[r]-sum[l-1]<<endl; } return 0; }