Code

#include <bits/stdc++.h>
using namespace std;

class SegmentTree {
  public:
    int n;
    vector<long long> t;
    SegmentTree(int n) {
        this->n = n;
        t.resize(4 * n + 1);
    }

    void build(vector<long long> &a, int v, int tl, int tr) {
        if (tl == tr) {
            t[v] = a[tl];
            return;
        }

        int tm = (tl + tr) / 2;
        build(a, 2 * v, tl, tm);
        build(a, 2 * v + 1, tm + 1, tr);
        t[v] = t[2 * v] + t[2 * v + 1];
    }

    long long query(int v, int tl, int tr, int l, int r) {
        if (l > r) {
            return 0;
        }
        if (tl == l && tr == r) {
            return t[v];
        }

        int tm = (tl + tr) / 2;
        auto left = query(2 * v, tl, tm, l, min(tm, r));
        auto right = query(2 * v + 1, tm + 1, tr, max(tm + 1, l), r);
        return left + right;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    SegmentTree st(n);
    st.build(a, 1, 0, n - 1);

    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;

        cout << st.query(1, 0, n - 1, l, r) << "\n";
    }

    return 0;
}