Segment tree and tree array template (copy and paste are really easy to use)

Line segment tree

contain lazy Mark pushdown

struct segtree
{
    
    struct tree {
    
        int l, r;
        //maintain something
    }tr[N << 2];
    inline void pushup(int u) {
    
        //maintain something
    }
    inline void pushdown(tree& node, tree& le, tree* re) {
    
        //maintain something
    }
    inline void pushdown(int u) {
    
        //maintain something
    }
    void build(int u, int l, int r) {
    
        tr[u] = {
     l,r };  //assign something
        if (l == r) {
    
            tr[u] = {
     l,r };  //assign something
            return;
        }
        int mid = l + r >> 1;
        build(ul, l, mid), build(ur, mid + 1, r);
        pushup(u);
    }
    void modify(int u, int l, int r, int v) {
    
        if (tr[u].l >= l && tr[u].r <= r) {
    
            //return something
            return;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        if (l <= mid)modify(ul, l, r, v);
        if (r > mid)modify(ur, l, r, v);
        pushup(u);
    }
    int query(int u, int l, int r) {
    
        if (tr[u].l >= l && tr[u].r <= r) {
    
            //return something
            return 1;
        }
        int mid = tr[u].l + tr[u].r >> 1;
        pushdown(u);
        int t = 0;
        if (l <= mid)t = query(ul, l, r);
        if (r > mid)t = query(ur, l, r);
        return t;
    }
}tr;

Tree array

Maintain prefix and only , Section sum, Be careful n The scope of the

struct BIT
{
    
    int tr[N];
    inline void ub(int& x) {
     x += x & (-x); }
    inline void db(int& x) {
     x -= x & (-x); }
    inline void modify(int x, int t) {
     for (; x <= n; ub(x))tr[x] += t; }
    inline int query(int x) {
    
        int res = 0;
        for (; x > 0; db(x))res += tr[x];
        return res;
    }
}bt;