ALGO Segment Tree (Recursive)

#include <iostream>
#include <cassert>
using namespace std;

namespace Mlxa {
    #define read cin
    #define eol '\n'
    #define endln cout << eol
    #define print(a) cout << a << ' ';
    template <class T> inline void
    println (T t) { cout << t << eol; }
    template <class A, class... B> inline void
    println (A a, B... b) { print(a); println(b...); }
    template <class I> inline void
    printseq (I b, I e) {
        for (I i(b); i != e; ++i)
            print(*i); endln;
    }
} using namespace Mlxa;

typedef long long ll;
const ll Size (4 * 1000 * 1000);
ll arr[Size];

namespace DO {
    ll binN (0);
    inline ll bin (ll a, ll b) { return a + b; }

    ll val[Size], lb[Size], rb[Size];

    ll build (ll v, ll l, ll r) {
        assert(l <= r);
        lb[v] = l, rb[v] = r; ll m = (l + r) / 2;
        if (l == r) val[v] = arr[l];
        else val[v] = bin(  build(2*v + 1, l, m),
                            build(2*v + 2, m + 1, r) );
        return val[v];
    }

    void upd_p (ll cur, ll p, ll add) {
        ll l(lb[cur]), r(rb[cur]);
        assert(l < cur && cur < r);
        if (l == r) {
            val[cur]+= add;
            arr[l]  += add;
        }
        ll m = (l + r) / 2;
        if (p <= m) upd_p(cur*2+1, p, add);
        else        upd_p(cur*2+2, p, add);
    }

    ll query (ll v, ll l, ll r) {
        ll mb = (lb[v] + rb[v]) / 2;
        if (lb[v] == l && rb[v] == r) return val[v];
        if (l > r) return binN;
        ll lres = query(v*2 + 1, max(l,  lb[v]), min(r, mb));
        ll rres = query(v*2 + 2, max(l, mb + 1), min(r, rb[v]));
        return bin( lres, rres );
    }
}

using namespace DO;
int main () {
    ll N; read >> N;
    for (ll i(0); i < N; ++i) read >> arr[i];
    build(0, 0, N-1); printseq(val, val + 4*N);
    ll a, b;
    while (read >> a >> b) {
        println(query(0, a, b));
    }
    return 0;
}