1、前缀和算法:用于优化频繁计算任意区间和。可将枚举算法的时间复杂度,降低到的级别
2、算法思想
(1)首先将原数组a转换为前缀和数组b。转换公式为:b[i] = b[i-1] +a[i];
(2)计算原数组a中下标l到r之间所有元素之和,转换为,前缀和数组b中下标r和l-1的元素之差,即b[r] – b[l-1] = a[l] + a[l+1] + … + a[r]
3、#10823. 前缀和【模板】
int a[1000001], b[1000001];
int main(){
int n,m,l,r;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) b[i]=a[i]+b[i-1]; // 建立前缀和数组b
for(int i=1;i<=m; i++) {
cin>>l>>r;
cout<<b[r] - b[l - 1]; // 计算l到r的区间和
}
return 0;
}