题目描述

输入一个长度为n的整数序列。

接下来再输入m个询问，每个询问输入一对l, r。

对于每个询问，输出原序列中从第l个数到第r个数的和。

解法：
先求出前n项和，然后s[r]-s[l-1]=a[r]+…+a[l];

样例

include[HTML_REMOVED]

using namespace std;

const int N=1e5+10;
int a[N];
//int prex_sum[N];
int n,m;

int main(){
cin>>n>>m;

a[0]=0;

for(int i=1;i<=n;i++)   scanf("%d",&a[i]);

for(int i=1;i<=n;i++)   a[i]=a[i-1]+a[i];

while(m--){
    int l,r;
    cin>>l>>r;

    cout<<a[r]-a[l-1]<<endl;
}

}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla