Segment Tree Node w/o build function

seg_tree_node.cpp

struct node
{
    T val, tag_update, tag_modify;
    bool modified;
    node *nl, *nr;
    node()
    {
        val = tag_update = modified = 0;
        nl = nr = nullptr;
    }
    void pull()
    {
        val = nl->val + nr->val;
    }
    void push(int l, int r)
    {
        int m = (l + r) >> 1;
        if (modified)
        {
            if (l != r)
            {
                nl->tag_modify = nr->tag_modify = tag_modify;
                nl->tag_update = nr->tag_update = 0;
                nl->modified = nr->modified = true;
                nl->val = tag_modify * (m - l + 1);
                nr->val = tag_modify * (r - m);
            }
            modified = false;
            tag_modify = tag_update = 0;
            return;
        }
        if (tag_update)
        {
            if (l != r)
            {
                nl->tag_update += tag_update;
                nr->tag_update += tag_update;
                nl->val += tag_update * (m - l + 1);
                nr->val += tag_update * (r - m);
            }
            tag_update = 0;
            return;
        }
    }
    T query(int ql, int qr, int l, int r)
    {
        if (ql > r || qr < l)
            return 0;
        if (ql <= l && r <= qr)
            return val;
        push(l, r);
        int m = (l + r) >> 1;
        return nl->query(ql, qr, l, m) + nr->query(ql, qr, m + 1, r);
    }
    // 加值
    void update(int ql, int qr, int d, int l, int r)
    {
        if (ql > r || qr < l)
            return;
        if (ql <= l && r <= qr)
        {
            tag_update += d;
            val += d * (r - l + 1);
            return;
        }
        push(l, r);
        int m = (l + r) >> 1;
        nl->update(ql, qr, d, l, m);
        nr->update(ql, qr, d, m + 1, r);
        pull();
    }
    // 改值
    void modify(int ql, int qr, int k, int l, int r)
    {
        if (ql > r || qr < l)
            return;
        if (ql <= l && r <= qr)
        {
            tag_update = 0;
            tag_modify = k;
            modified = true;
            val = k * (r - l + 1);
            return;
        }
        push(l, r);
        int m = (l + r) >> 1;
        nl->modify(ql, qr, k, l, m);
        nr->modify(ql, qr, k, m + 1, r);
        pull();
    }
};