题目：

输入N个整数的数组A，每个询问给2个整数a和b，问数组的第a个到第b个的和是多少？

这道题目显然就是一个累加算法，输入完数组后，用a到b的循环即可。

for(int i=a;i<=b;++i)

s=s+shu[i];

但如果题目变成：

输入N个整数的数组A，然后有M个询问。每个询问给2个整数a和b，问数组的第a个到第b个的和是多少？

请问怎么做?

通常做法是，在求和循环外再增加一个次数循环。

for(int j=1;j<=m;++j)

{

cin>>a>>b;s=0;

for(int i=a;i<=b;++i)

s=s+shu[i];

}

再增加点难度！

N和M，N、M的范围在[1,100000]。

请问用上述双重循环是否会超时？？

100000*100000=10^10>10^8 超时！

所以我们该如何进行优化呢？

这时候，我们来看一下，如果输入的a跟b都是1-100，那我们不就得重复算多遍shu[1]-shu[100]吗？如果能记录下第一次算出shu[1]-shu[100]的和，那下次要算的时候我们就能直接调用。

S[1,100]？？？

显然，我们不能这样定义，所以这里我们引入前缀和

s[i] 数组记录1-i的和，即s[100]为shu[1]-shu[100]的和。

请问s[30]为？？

计算前缀和：

for(int i=1;i<=n;++i)

s[i]=s[i-1]+shu[i];

原理：s[i]表示第1个数到第i个数的和，即s[i]=shu[1]+shu[2]+...+shu[i-1]+shu[i];

从表达式中，我们可以看到shu[1]+shu[2]+...+shu[i-1]其实是第1个数到第i-1个数的和，即为s[i-1]。

所以可转换表达式为：

s[i]=shu[1]+shu[2]+...+shu[i-1]+shu[i];

  =s[i-1]+shu[i];

使用前缀和：

计算shu[a]---shu[b]的和  cout<<s[b]-s[a-1];

计算shu[5]---shu[20]的和  cout<<s[20]-s[5-1];