前缀和

公式： s[i] = s[i-1]+a[i];
用途： 求一段连续的前缀和复杂度为o(1)

代码:

_#include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

include [HTML_REMOVED]

using namespace std;
int n, m;
const int N = 100010;
int a[N];
int b[N];

int main()
{
cin >> n >>m;
b[0]=0;
for(int i=1;i<=n;i)scanf(“%d”,&a[i]);
for(int i =1;i<=n;i)b[i]=b[i-1]+a[i];
while(m–)
{
int l,r;
scanf(“%d%d”,&l,&r);
printf(“%d\n”,b[r] - b[l-1]);
}
return 0;
}_