综合：前缀和区间和

运行下面这段程序：

综合：前缀和 / 树状数组 / 线段树 / ST 表，按题目要求选对结构。

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

vector<long long> prefix(const vector<int>& a) {
    // 前缀和数组：p[i] = a[0] + ... + a[i-1]
    vector<long long> p(a.size() + 1, 0);
    for (size_t i = 0; i < a.size(); i++) {
        p[i + 1] = p[i] + a[i];
    }
    return p;
}

long long range_sum(const vector<long long>& p, int l, int r) {
    // 用前缀和 O(1) 求 a[l..r]（闭区间）的和
    return p[r + 1] - p[l];
}

int main() {
    cout << range_sum(prefix({5, 3, 8, 1, 9}), 1, 3) << endl;
}

（本题用 g++ -std=c++17 -O0 编译。）