前缀和算法的主要用处:频繁计算任意区间和。
总体思路:先把每个元素的前缀和计算出来,然后每个区间和可以通过两个和之差求得,即 [l,r]区间和的计算公式:b[r] - b[l-1]
int n,m;
int a[100001];
int b[100001]; // 用于存放每个元素的前缀和
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
b[i]=b[i-1]+a[i]; // 计算第 i 个元素的前缀和,其中:b[0] = 0; b[n] 是所有元素的和。
}
int l, r;
for(int i=1; i<=m; i++)
{
cin>>l>>r;
cout<<b[r]-b[l-1]<<endl; // 直接计算区间[l, r]的和
}
return 0;
}