算法题：前缀和I

问题描述

给出 n个整数 a[1],a[2],…,a[n].

q次查询，每次查询给出一个整数 p，要求输出 ∑^p~i=1~a[i].

输入格式

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

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

接下来q 行，每行有一个整数 p表示查询 ∑^p~i=1~a[i].

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

1≤p≤n.

输出格式

对于每组询问输出一个整数代表 ∑^p~i=l~a[i]的值。

样例

输入

5 2
1 4 2 3 1
2
5

输出

5
11

解决方案

思路

前缀和

代码

#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 r, t;
        cin >> r;
        t = sum[r - 1];
        cout << t << endl;
    }
    return 0;
}