【李老师】CSP200-第13课：前缀和

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++) {   // 建立前缀和数组b
        cin>>a[i];    
        b[i]=a[i]+b[i-1];
    }
    for(int i=1;i<=m; i++) {
    	        cin>>l>>r;	
	 	cout<<b[r] - b[l - 1]<<endl;	 // 计算l到r的区间和
	}
    return 0;
}