Compact recursive implementation of basic Segment Tree.

SegmentTree.cc

template <typename T>
struct SegmentTree {
    int n;
    T* t;
    T zero_val;

    inline T merge(T a, T b)
    {
        return a + b; // MODIFY FOR EACH PROBLEM
    }
    void update(int node, int l, int r, int i, T v)
    {
        if (l > i or r < i) return; // Interval outside query
        if (l == r) { // leaf node
            t[node] = v; // MODIFY FOR EACH PROBLEM
            return;
        }
        int m = (l+r)/2;
        update(2*node, l, m, i, v);
        update(2*node+1, m+1, r, i, v);
        t[node] = merge(t[2*node], t[2*node+1]);
    }
    T query(int node, int l, int r, int i, int j)
    {
        if (l > j or r < i) return 0; // Interval outside query. MODIFY FOR EACH PROBLEM
        if (l >= i and r <= j) return t[node]; // Interval completely inside query
        int m = (l+r)/2;
        return merge(query(2*node, l, m, i, j), query(2*node+1, m+1, r, i, j));
    }
    void build(T node, int l, int r, int arr[])
    {
        if (l == r) { // leaf node
            t[node] = arr[l];
            return;
        }
        int m = (l+r)/2;
        build(2*node, l, m, arr);
        build(2*node+1, m+1, r, arr);
        t[node] = merge(t[2*node], t[2*node+1]);
    }
    void setup(int n_, T zero_val_)
    {
        n = n_;
        zero_val = zero_val_;
        t = new T[4*n];
        memset(t, 0, 4*n*sizeof(T));
    }
    inline void build(T arr[]) { build(1, 0, n-1, arr); }
    inline void update(int i, T v) { update(1, 0, n-1, i, v); }
    inline T query(int i, int j) { return query(1, 0, n-1, i, j); }
};