支持动态修改的线段树

动态修改

作为一颗线段树，如果它只能查询而不能修改，就很容易被上位替代，而支持在$O(\log n)$ 下进行区间修改和区间查询，则是线段树最大的优势

要实现区间修改，我们需要引入 lazy propagation即懒标记

懒标记的作用我们用如下例子表示：

假设我们需要对区间 [2,5] 的元素都+10，且当前节点[1,8] 覆盖了 [2,5]

我们可以：

• 不立即递归更新子节点
• 在当前节点打上懒标记
• 记录这个区间整体应该要+10
• 只有当 下次访问到这个区间的子节点的时，才下传这个标记

变化

和支持区间查询的线段树的线段树相比，我们的结构体的存储信息应该多加上懒标记的信息

同时我们需要多加一些函数来应用和下传懒标记，以及区间修改

我们这次以支持模下运算的加法和乘法演示

struct Seg
{
    struct Node
    {
        i64 sum = 0, add = 0, mul = 1;
    };
    i64 n;
    i64 mod;
    vector<Node> seg;
    Seg(i64 n, i64 mod)
    {
        this->n = n;
        this->mod = mod;
        seg.resize((n << 2) + 4);
    }
    // 合并逻辑
    Node merge(const Node &L, const Node &R)
    {
        Node res;
        res.sum = (L.sum + R.sum) % mod;
        res.add = 0;
        res.mul = 1;
        return res;
    }
    //懒标记应用
    void applyadd(i64 idx, i64 l, i64 r, i64 val)
    {
        seg[idx].add = (seg[idx].add + val) % mod;
        seg[idx].sum = (seg[idx].sum + val * (r - l + 1) % mod) % mod;
    }
    void applymul(i64 idx, i64 l, i64 r, i64 val)
    {
        seg[idx].mul = (seg[idx].mul * val) % mod;
        seg[idx].sum = seg[idx].sum * val % mod;
        seg[idx].add = seg[idx].add * val % mod;
    }
    // 懒标记向下应用
    void push(i64 idx, i64 l, i64 r)
    {
        i64 &_add = seg[idx].add;
        i64 &_mul = seg[idx].mul;
        if (_add == 0 && _mul == 1) return;
        i64 mid = (l + r) >> 1;
        applymul(idx << 1, l, mid, _mul);
        applymul(idx << 1 | 1, mid + 1, r, _mul);
        applyadd(idx << 1, l, mid, _add);
        applyadd(idx << 1 | 1, mid + 1, r, _add);
        _add = 0;
        _mul = 1;
    }
    void build(i64 idx, i64 l, i64 r, const vint &a)
    {
        if (l == r) {
            seg[idx].sum = a[l];
            seg[idx].add = 0;
            return;
        }
        i64 mid = (l + r) >> 1;
        build(idx << 1, l, mid, a);
        build(idx << 1 | 1, mid + 1, r, a);
        seg[idx] = merge(seg[idx << 1], seg[idx << 1 | 1]);
    }
    // 1是加法，2是乘法
    void update(i64 idx, i64 l, i64 r, i64 ql, i64 qr, i64 val, i64 op)
    {
        if (op == 1) {
            if (ql <= l && r <= qr) {
                applyadd(idx, l, r, val);
                return;
            }
        }
        if (op == 2) {
            if (ql <= l && r <= qr) {
                applymul(idx, l, r, val);
                return;
            }
        }
        push(idx, l, r);
        i64 mid = (l + r) >> 1;
        if (ql <= mid) update(idx << 1, l, mid, ql, qr, val, op);
        if (qr > mid) update(idx << 1 | 1, mid + 1, r, ql, qr, val, op);
        seg[idx] = merge(seg[idx << 1], seg[idx << 1 | 1]);
    }
    Node query(i64 idx, i64 l, i64 r, i64 ql, i64 qr)
    {
        if (ql <= l && r <= qr) return seg[idx];
        push(idx, l, r);
        i64 mid = (l + r) >> 1;
        i64 res = 0;
        if (qr <= mid)
            return query(idx << 1, l, mid, ql, qr);
        else if (ql > mid)
            return query(idx << 1 | 1, mid + 1, r, ql, qr);
        else
            return merge(query(idx << 1, l, mid, ql, qr), query(idx << 1 | 1, mid + 1, r, ql, qr));
    }
    void build(const vint &a)
    {
        build(1, 1, n, a);
    }
    void update(i64 l, i64 r, i64 val, i64 op)
    {
        update(1, 1, n, l, r, val, op);
    }
    i64 query(i64 l, i64 r)
    {
        return query(1, 1, n, l, r).sum % mod;
    }
};

其实主要思想就是懒标记的使用和下传