前缀和

如果对于一组数据，我们需要在时间复杂度O(1)内求出一个区间内的和。

常规思路，是给出一个区间，然后挨个去加上，然后输出结果。

但是，这种写法很容易超时，这时，就需要一个前缀和，可以很轻松的解决这个问题。

前缀和的核心就是下面的公式
$$
a_n = a_{n-1} + a_n
$$
也就是，对于下标 k ，a[k] 是 前 k 个数的和，这时只需要做减法就可以得到答案

C++

#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int cot[N];

void solve()
{
    //n是数组内的数的个数，m则是询问的次数
   int n, m;
   cin >> n >> m;
   // 这里认为l 和 r的大小是从1到1e5
   for(int i = 1;i <= n; i ++)
   {
        cin >> cot[i];
        cot[i] = cot[i - 1] + cot[i];
   }
   while(m --)
   {
        int l, r;
        cin >> l >> r;
        cout << cot[r] - cot[l - 1] << endl;
   }
}
int main()
{
    solve();
}

C

#include<stdio.h>
#define N 100010
int a[N];
int main()
{
	int n, m;
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= n;i ++)
	{
		scanf("%d",&a[i]);
		a[i] = a[i - 1] + a[i];
	}
	while(m --)
	{
		int l, r;
		scanf("%d%d",&l,&r);
		printf("%d\n",a[r] - a[l - 1]);
	}
	return 0;
}