seg_t.cpp

#include "bits/stdc++.h"

template<typename T>
std::vector<T> dibs(size_t n){
    std::vector<T> ans;
    ans.reserve(n);
    return ans;
}

template<typename Monoid>
struct seg_t {
    using M = typename Monoid::M;
    struct reference {
        operator M() { return seg.tree[seg.n + i]; }
        reference& operator=(const M& val){
            seg.tree[seg.n + i] = val;
            for(size_t p = seg.n + i; p >> 1; p >>= 1)
                seg.tree[p>>1] = Monoid::combine(seg.tree[p&(~1)], seg.tree[p|1]);
            return *this;
        }
        seg_t& seg;
        size_t i;
    };

    seg_t(size_t n) : n(n), tree(2 * n, Monoid::e) {}
    seg_t(std::vector<M>&& x) : n(x.size()) {
        x.insert(begin(x), n, Monoid::e);
        tree = x;
        build();
    }
    seg_t(const std::vector<M>& x) : n(x.size()), tree(dibs<M>(2 * n)) {
        tree.resize(n);
        std::copy(begin(x), end(x), back_inserter(tree));
        build();
    }

    M query(size_t l, size_t r) const {
        M lans = Monoid::e;
        M rans = Monoid::e;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1){
            if(l&1) lans = Monoid::combine(lans, tree[l++]);
            if(r&1) rans = Monoid::combine(tree[--r], rans);
        }
        return Monoid::combine(lans, rans);
    }

    reference operator[](size_t i){ return {*this, i}; }

    size_t n = 0;
    std::vector<M> tree;
private:
    void build(){
        for(size_t i = n - 1; 1 + i; --i)
            tree[i] = Monoid::combine(tree[i<<1], tree[i<<1|1]);
    }
};

struct Sum{
    using M = int32_t;
    constexpr static M e = 0;
    static M combine(const M& a, const M& b){
        return a + b;
    }
};

using namespace std;
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);

    int n;
    std::cin >> n;
    auto x(dibs<int32_t>(n));
    std::copy_n(istream_iterator<int>(cin), n, back_inserter(x));

    seg_t<Sum> tree(x);

    for(int i = 0; i < n; i++)
        for(int j = i + 1; j <= n; j++)
            cout << i << " " << j << ": " << tree.query(i, j) << endl;
}