算法分析

主要记住如下的两个公式：

​ S[i] = a[1] + a[2] + ... a[i]
​ a[l] + ... + a[r] = S[r] - S[l - 1]

类似于求斐波那契数列和杨辉三角的方法一样，从而以 $O(1)$ 的时间复杂度求出每一次的结果

代码

#include<iostream>
using namespace std;
const int N = 100010;
int n, m, a[N], s[N];

int main(){

    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) s[i] = s[i-1] + a[i];

    while(m--)
    {
        int l,r;
        cin>>l>>r;
        cout<<s[r]-s[l-1]<<endl;
    }
    return 0;
}