Segment Tree

#include<bits/stdc++.h>
#define ll long long

template <typename T> 
struct SegmentTree
{
    int n;
    T *seg_v;
    T *seg_more;
    
    void init(int n_) {
        
        n = n_;
        seg_v     = new T[n*4+5];
        seg_more  = new T[n*4+5];
        
        fill(seg_v,     seg_v     + n*4+5, 0);
        fill(seg_more , seg_more  + n*4+5, 0);
        
    }
    
    void build (int id, int l, int r) {
        if (l == r) {
            // TODO: set seg_v[id] using a[id] or hld.inarray_inv[id]
            seg_v[id] = 0;
            // ====
        }
        else {
            int mid = (l+r)/2;
            build(id*2, l, mid);
            build(id*2+1, mid+1, r);
            // TODO: update seg_v[id] by seg_v[id*2] and seg_v[id*2+1]
            seg_v[id] = 0;
            // ====
        }
    }
    
    void lazy_prop(int id, int l, int r) {
        // TODO: lazy propagate from seg_more[id] to:
        //          seg_v[id*2], seg_more[id*2], 
        //          seg_v[id*2+1], seg_more[id*2+1]. 
        //       Then set seg_more[id] to 0.
        int mid = (l+r)/2;
        seg_v[id*2]   = seg_v[id*2] + seg_more[id];
        seg_v[id*2+1] = seg_v[id*2+1] + seg_more[id];
        seg_more[id*2]   = seg_more[id*2] + seg_more[id];
        seg_more[id*2+1] = seg_more[id*2+1] + seg_more[id];
        seg_more[id] = 0;
        // ====
    }
    
    void update (int id, int l, int r, int min_range, int max_range, T val) {
        if (min_range <= l && r <= max_range) {
            // TODO: update seg_v[id], seg_more[id]
            seg_v[id] += val;
            seg_more[id] += val;
            // ====
            return;
        }
        
        if (max_range < l || min_range > r) {
            return;
        }
        
        if (seg_more[id] != 0)
            lazy_prop(id, l, r);
                
        int mid = (l+r)/2;
        update(id*2, l, mid, min_range, max_range, val);
        update(id*2+1, mid+1, r, min_range, max_range, val);
        // TODO: update current node based on its 2 children
        seg_v[id] = min(seg_v[id*2], seg_v[id*2+1]);
        // ====
    }
    
    T query(int id, int l, int r, int min_range, int max_range) {
        if (min_range <= l && r <= max_range) {
            // TODO: return value using seg_v[id]
            return seg_v[id];
            // ====
        }
        
        if (max_range < l || min_range > r) {
            // TODO: return a default value
            return 0;
        }
        
        if (seg_more[id] != 0)
            lazy_prop(id, l, r);
        
        int mid = (l+r)/2;
        T res1 = query(id*2, l, mid, min_range, max_range);
        T res2 = query(id*2+1, mid+1, r, min_range, max_range);
        
        // TODO: return combined value of res1 and res2
        T res = res1 + res2;
        return res;
        // ====
    }
};