template<typename T>
class TSegmentTree {
public:
    TSegmentTree(size_t size, T zeroValue)
        : Size_(size)
        , ZeroValue_(zeroValue)
    {
        Tree_.assign(size * 4, ZeroValue_);
    }

    void update(size_t v, size_t tl, size_t tr, size_t i, T value) {
        if (tl >= r || tr <= l) {
            return;
        }
        if (tl >= l && tr <= r) {
            t[v] += value;
        } else {
            size_t tm = (tl + tr) / 2;
            if (i < tm) {
                update(v * 2 + 1, tl, tm, i, value);
            } else {
                update(v * 2 + 2, tm, tr, i, value);
            }
            t[v] = t[v * 2 + 1] + t[v * 2 + 2];
        }
    }

    T get(size_t v, size_t tl, size_t tr, size_t l,  size_t r) {
        if (tl >= r || tr <= l) {
            return ZeroValue_;
        }
        if (tl >= l && tr <= r) {
            return t[v];
        } else {
            size_t tm = (tl + tr) / 2;
            T answer = get(v * 2 + 1, tl, tm, l, r) + get(v * 2 + 2, tm, tr, l, r);
            return answer;
        }
    }

private:
    TVector<T> Tree_;
    size_t Size_;
    T ZeroValue_;
};