Segment Tree

// 1 based, [1, n]
template<typename T>
struct SegTree{
    int sz;
    vector<T> tree;
    SegTree(int n):sz(n),tree(4*n+4){}
    void update(int node, int s, int e, int i, T v){
        if(s == e){ tree[node] = v; return; }
        int m = (s + e) / 2;
        if(i <= m) update(node*2, s, m, i, v);
        else update(node*2+1, m+1, e, i, v);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
    T query(int node, int s, int e, int l, int r){
        if(r < s || e < l) return 0;
        if(l <= s && e <= r) return tree[node];
        int m = (s + e) / 2;
        return query(node*2, s, m, l, r) + query(node*2+1, m+1, e, l, r);
    }
    void Update(int i, T v){ update(1, 1, sz, i, v); } // i번째 수를 v로 갱신
    T Query(int l, int r){ return query(1, 1, sz, l, r); } // [l, r]번째 수의 합
};
////
// SegTree<ll> seg(N);
// seg.Update(i, v);
// seg.Query(l, r);
 
// 1 based, [1, n], 구간에 더하는 갱신이 필요할 때 (HLD 경로 업데이트 등)
template<typename T>
struct LazySegTree{
    int sz;
    vector<T> tree, lazy;
    LazySegTree(int n):sz(n),tree(4*n+4),lazy(4*n+4){}
    void push(int node, int s, int e){
        if(lazy[node] == 0) return;
        tree[node] += (T)(e - s + 1) * lazy[node];
        if(s != e) lazy[node*2] += lazy[node], lazy[node*2+1] += lazy[node];
        lazy[node] = 0;
    }
    void update(int node, int s, int e, int l, int r, T v){
        push(node, s, e);
        if(r < s || e < l) return;
        if(l <= s && e <= r){ lazy[node] += v; push(node, s, e); return; }
        int m = (s + e) / 2;
        update(node*2, s, m, l, r, v);
        update(node*2+1, m+1, e, l, r, v);
        tree[node] = tree[node*2] + tree[node*2+1];
    }
    T query(int node, int s, int e, int l, int r){
        push(node, s, e);
        if(r < s || e < l) return 0;
        if(l <= s && e <= r) return tree[node];
        int m = (s + e) / 2;
        return query(node*2, s, m, l, r) + query(node*2+1, m+1, e, l, r);
    }
    void RangeAdd(int l, int r, T v){ update(1, 1, sz, l, r, v); } // [l, r]에 v를 더함
    T Query(int l, int r){ return query(1, 1, sz, l, r); } // [l, r]번째 수의 합
};
////
// LazySegTree<ll> seg(N);
// seg.RangeAdd(l, r, v);
// seg.Query(l, r);