Segment Tree

template<typename T>
struct SegTree {
    int n;
    vector<T> tree;
    T (*op)(T, T);
    T neutral;
    SegTree(int _n, T (*_op)(T, T), T _neutral) : n(_n), op(_op), neutral(_neutral) {
        tree.assign(2 * n, neutral);
    }
    void update(int idx, T val) {
        for (tree[idx += n] = val; idx > 1; idx >>= 1)
            tree[idx >> 1] = op(tree[idx], tree[idx ^ 1]);
    }
    T query(int l, int r) {
        T resL = neutral, resR = neutral;
        for (l += n, r += n + 1; l < r; l >>= 1, r >>= 1) {
            if (l & 1) resL = op(resL, tree[l++]);
            if (r & 1) resR = op(tree[--r], resR);
        }
        return op(resL, resR);
    }
};