题目描述

众所周知，狮均国内吼叫总值（Real GDS per lion）是衡量一个狮子国狮子健康程度的重要指标。

其计算方法为：选取若干个狮子，将每个狮子吼叫的次数相加即为总值。

叶子是狮子国健康委员会的会长，有人举报小林汇报的狮均国内吼叫总值的数据有误，所以他想请你帮忙计算。

具体来说，你会知道编号为 1 到 n 的 n 只狮子吼叫的次数 ai。

叶子会提出 q 个问题。对于每个问题他会给出 l 和 r。

他想知道编号在 l 和 r 之间的狮子的狮均国内吼叫总值。

简化题目

求$a[i]$的前缀和数组中第 $l$ 位到第 $r$ 位的值。

算法1

(前缀和) $O(n^2)$

C++ 代码

#include <bits/stdc++.h>

using namespace std ;

const int N = 1e6 + 1 ;

int n , q ;
int a[N] ;
int s[N] ;

int main ( ) {

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

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

    cin >> q ;
    for ( int i = 1 ; i <= q ; i ++ ) {

        int l , r ;
        cin >> l >> r ;

        cout << s[r] - s[l - 1] << endl ;

    }

    return 0 ;

}