算法题：前缀和II

问题描述

给出 n个整数 a[1],a[2],…,a[n].
q次查询，每次查询给出两个整数 l,r，要求输出 ∑^r_i=la[i].

输入格式

第一行有两个正整数， n表示数组长度， q表示询问次数.

第二行有n 个整数 a[1],a[2],…,a[n].

接下来q 行，每行有两个整数 l,r表示查询 ∑^r_i=la[i].

1≤n,a[i],q≤10⁵.

1≤l≤r≤n.

输出格式

对于每组询问输出一个整数代表 ∑^r_i=la[i]的值.

样例

输入

5 2
1 4 2 3 1
1 2
3 5

输出

5
6

解决方案

思路

前缀和

代码

#include <iostream>

using namespace std;

int arr[100000];

int main() {
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    // 前缀和计算
    auto &sum = arr;    //与arr共用一块空间
    sum[0] = arr[0];
    for (int i = 1; i < n; ++i) {
        sum[i] = arr[i] + sum[i - 1];
    }

    // 区间和
    for (int i = 0; i < q; ++i) {
        int l, r, t;
        cin >> l >> r;
        t = sum[r - 1];
        if (l != 1)
            t -= sum[l - 1 - 1];

        cout << t << endl;
    }
    return 0;
}