之前写线段树一直没有封装成一个 Info 的意识，每次要改好多好多行，而且其中很多都是无用修改；今天一时兴起查了一下 jly 的板子，发现这种类模板真的非常 nice，稍微改改结点里的变量和加操作就彳亍，其他部分完全不需要做改动。

一、不带懒标记的线段树 —— 单点修改，区间查询 SegmentTree -> SGT

• jls 的板子是左闭右开的，比如要查询的区间是 $[l, \ r]$，那么进入函数变量的应该是 $l$ 和 $r + 1$。

• 我根据自己的习惯改了改左儿子和右儿子的写法，这个倒是随意。

• 每次在 $query$ 的开始就判断查询的区间是否合法（相当于少去 y 总模板里的 $l \leqslant mid$ 和 $r \gt mid$，多递归一层），不合法就返回 Info 的默认值，因此 Info 默认值的设置要看求的是和（设为 $0$），还是最大值（设为 $-inf$），还是最小值（设为 $inf$）。

template<class Info>
struct SGT {
    #define l(p) (p << 1)
    #define r(p) (p << 1 | 1)
    int n;
    std::vector<Info> info;
    SGT() {}
    SGT(int _n, Info _v = Info()) {
        init(_n, _v);
    }
    template<class T>
    SGT(std::vector<T> _init) {
        init(_init);
    }
    void init(int _n, Info _v = Info()) {
        init(std::vector(_n, _v));
    }
    template<class T>
    void init(std::vector<T> _init) {
        n = _init.size();
        info.assign(4 << std::__lg(n), Info());
        auto build = [&](auto self, int p, int l, int r) {
            if (r - l == 1) {
                info[p] = _init[l];
                return;
            }
            int m = l + r >> 1;
            self(self, l(p), l, m);
            self(self, r(p), m, r);
            pull(p);
        };
        build(build, 1, 0, n);
    }
    void pull(int p) { // 这个就是 y 总的 pushup
        info[p] = info[l(p)] + info[r(p)];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = l + r >> 1;
        if (x < m) {
            modify(l(p), l, m, x, v);
        } else {
            modify(r(p), m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y or r <= x) {
            return Info();
        }
        if (l >= x and r <= y) {
            return info[p];
        }
        int m = l + r >> 1;
        return query(l(p), l, m, x, y) + query(r(p), m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    #undef l(p)
    #undef r(p)
};

struct Info {
    // 定义要存的变量，比如区间和 sum 或者最大公约数 d 等等，至于下标就不用存了
};
Info operator+(Info a, Info b) {
    Info c;
    // 对 a（左儿子） 和 b（右儿子） 一通操作合成 c（父结点）
    return c;
}

例题1：AcWing 246. 区间最大公约数

思路大家可以简略过一遍，就是用到了最大公约数的差分性质。

这题需要维护的信息有区间和 $sum$ 和区间最大公约数 $d$，默认值为 $0$，如下所示

struct Info {
    LL sum, d;
    Info(LL s = 0): sum(s), d(s) {}
};
Info operator+(Info a, Info b) {
    Info c;
    c.sum = a.sum + b.sum;
    c.d = std::gcd(a.d, b.d);
    return c;
}

完整代码

#include <bits/stdc++.h>

using LL = long long;

template<class Info>
struct SGT {
    #define l(p) (p << 1)
    #define r(p) (p << 1 | 1)
    int n;
    std::vector<Info> info;
    SGT() {}
    SGT(int _n, Info _v = Info()) {
        init(_n, _v);
    }
    template<class T>
    SGT(std::vector<T> _init) {
        init(_init);
    }
    void init(int _n, Info _v = Info()) {
        init(std::vector(_n, _v));
    }
    template<class T>
    void init(std::vector<T> _init) {
        n = _init.size();
        info.assign(4 << std::__lg(n), Info());
        auto build = [&](auto self, int p, int l, int r) {
            if (r - l == 1) {
                info[p] = _init[l];
                return;
            }
            int m = l + r >> 1;
            self(self, l(p), l, m);
            self(self, r(p), m, r);
            pull(p);
        };
        build(build, 1, 0, n);
    }
    void pull(int p) {
        info[p] = info[l(p)] + info[r(p)];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = l + r >> 1;
        if (x < m) {
            modify(l(p), l, m, x, v);
        } else {
            modify(r(p), m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y or r <= x) {
            return Info();
        }
        if (l >= x and r <= y) {
            return info[p];
        }
        int m = l + r >> 1;
        return query(l(p), l, m, x, y) + query(r(p), m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    #undef l(p)
    #undef r(p)
};

struct Info {
    LL sum, d;
    Info(LL s = 0): sum(s), d(s) {}
};
Info operator+(Info a, Info b) {
    Info c;
    c.sum = a.sum + b.sum;
    c.d = std::gcd(a.d, b.d);
    return c;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    std::vector<Info> a(n);
    for (int i = 0; i < n; i += 1) {
        std::cin >> a[i].d;
    }
    a[0].sum = a[0].d;
    for (int i = n - 1; i > 0; i -= 1) {
        a[i].d -= a[i - 1].d;
        a[i].sum = a[i].d;
    }
    SGT<Info> sgt(a);
    while (m -- ) {
        char c;
        int l, r;
        std::cin >> c >> l >> r;
        if (c == 'Q') {
            std::cout << std::gcd(sgt.query(0, l).sum, sgt.query(l, r).d) << "\n";
        } else {
            LL d;
            std::cin >> d;
            l -= 1;
            sgt.modify(l, Info(a[l].d += d));
            if (r < n) {
                sgt.modify(r, Info(a[r].d -= d));
            }
        }
    }    

    return 0;
}

例题2：AcWing 245. 你能回答这些问题吗

这题需要维护四个变量：

• pre：表示当前区间的前缀最大和

• suf：表示当前区间的后缀最大和

• sum：表示当且区间的所有元素和

• res：表示当前区间的最大连续字段和

所以 Info 会被写成这种形状：

constexpr int inf = 2000;
struct Info {
    int pre, suf, sum, res;
    Info(int s = -inf): pre(s), suf(s), sum(s), res(s) {} // 单点的初值全部都一样
};
Info operator+(Info a, Info b) {
    Info c;
    c.sum = a.sum + b.sum;                           // 区间和
    c.pre = std::max(a.pre, a.sum + b.pre);          // 整个左半区间 + 右半区间前缀
    c.suf = std::max(b.suf, a.suf + b.sum);          // 左半区间后缀 + 整个右半区间
    c.res = std::max({a.res, b.res, a.suf + b.pre}); // 左半最大连续和 or 右半最大连续和 or 左后缀 + 右前缀
    return c;
}

完整代码

#include <bits/stdc++.h>

using LL = long long;

template<class Info>
struct SGT {
    #define l(p) (p << 1)
    #define r(p) (p << 1 | 1)
    int n;
    std::vector<Info> info;
    SGT() {}
    SGT(int _n, Info _v = Info()) {
        init(_n, _v);
    }
    template<class T>
    SGT(std::vector<T> _init) {
        init(_init);
    }
    void init(int _n, Info _v = Info()) {
        init(std::vector(_n, _v));
    }
    template<class T>
    void init(std::vector<T> _init) {
        n = _init.size();
        info.assign(4 << std::__lg(n), Info());
        auto build = [&](auto self, int p, int l, int r) {
            if (r - l == 1) {
                info[p] = _init[l];
                return;
            }
            int m = l + r >> 1;
            self(self, l(p), l, m);
            self(self, r(p), m, r);
            pull(p);
        };
        build(build, 1, 0, n);
    }
    void pull(int p) {
        info[p] = info[l(p)] + info[r(p)];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = l + r >> 1;
        if (x < m) {
            modify(l(p), l, m, x, v);
        } else {
            modify(r(p), m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y or r <= x) {
            return Info();
        }
        if (l >= x and r <= y) {
            return info[p];
        }
        int m = l + r >> 1;
        return query(l(p), l, m, x, y) + query(r(p), m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    #undef l(p)
    #undef r(p)
};

constexpr int inf = 2000;
struct Info {
    int pre, suf, sum, res;
    Info(int s = -inf): pre(s), suf(s), sum(s), res(s) {}
};
Info operator+(Info a, Info b) {
    Info c;
    c.sum = a.sum + b.sum;
    c.pre = std::max(a.pre, a.sum + b.pre);
    c.suf = std::max(b.suf, a.suf + b.sum);
    c.res = std::max({a.res, b.res, a.suf + b.pre});
    return c;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m;
    std::cin >> n >> m;

    std::vector<Info> a;
    for (int i = 0; i < n; i += 1) {
        int s;
        std::cin >> s;
        a.emplace_back(s);
    }
    SGT<Info> sgt(a);
    while (m -- ) {
        int k, x, y;
        std::cin >> k >> x >> y;
        if (k == 1) {
            if (x > y) {
                std::swap(x, y);
            }
            x -= 1;
            std::cout << sgt.query(1, 0, n, x, y).res << "\n";
        } else {
            x -= 1;
            sgt.modify(x, Info(y));
        }
    }

    return 0;
}

二、带懒标记的线段树 —— 区间修改，区间查询 LazySegmentTree -> LSGT

• 加了一个 Tag 来做向下传递的标记。

• 新加 $Apply$ 函数来做区间修改，修改时的操作封装于 Tag 和 Info 中的 $apply$ 函数中。

• $push$ 即为 y 总的 $pushdown$ 操作。

template<class Info, class Tag>
struct LSGT {
    #define l(p) (p << 1)
    #define r(p) (p << 1 | 1)
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LSGT() {}
    LSGT(int _n, Info _v = Info()) {
        init(_n, _v);
    }
    template<class T>
    LSGT(std::vector<T> _init) {
        init(_init);
    }
    void init(int _n, Info _v = Info()) {
        init(std::vector(_n, _v));
    }
    template<class T>
    void init(std::vector<T> _init) {
        n = _init.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        auto build = [&](auto self, int p, int l, int r) {
            if (r - l == 1) {
                info[p] = _init[l];
                return;
            }
            int m = l + r >> 1;
            self(self, l(p), l, m);
            self(self, r(p), m, r);
            pull(p);
        };
        build(build, 1, 0, n);
    }
    void pull(int p) {
        info[p] = info[l(p)] + info[r(p)];
    }
    void apply(int p, const Tag &v, int len) {
        info[p].apply(v, len);
        tag[p].apply(v);
    }
    void push(int p, int len) {
        apply(l(p), tag[p], len / 2);
        apply(r(p), tag[p], len - len / 2);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = l + r >> 1;
        push(p, r - l);
        if (x < m) {
            modify(l(p), l, m, x, v);
        } else {
            modify(r(p), m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y or r <= x) {
            return Info();
        }
        if (l >= x and r <= y) {
            return info[p];
        }
        int m = l + r >> 1;
        push(p, r - l);
        return query(l(p), l, m, x, y) + query(r(p), m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    void Apply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y or r <= x) {
            return;
        }
        if (l >= x and r <= y) {
            apply(p, v, r - l);
            return;
        }
        int m = l + r >> 1;
        push(p, r - l);
        Apply(l(p), l, m, x, y, v);
        Apply(r(p), m, r, x, y, v);
        pull(p);
    }
    void Apply(int l, int r, const Tag &v) {
        return Apply(1, 0, n, l, r, v);
    }
    #undef l(p)
    #undef r(p)
};

struct Tag {
    // 定义要下放什么标记
    Tag(...): ... {} // 初始化
    void apply(Tag t) {
        // 怎么用父结点的标记更新儿子的标记
    }
};
struct Info {
    int sum = 0;
    void apply(Tag t, int len) {
        // 怎么用父结点的标记更新儿子存储的信息
        // 这里 jls 原本没有区间长度 len 这个形参，但我觉得可能常用就自己加上了
    }
};
Info operator+(Info a, Info b) {
    Info c;
    // a 和 b 一通操作弄出 c
    return c;
}

例题：AcWing 1277. 维护序列

这题需要维护一个乘和一个加的标记，以及用 Info 存下区间和。

所以 Info 和 Tag 如下：

int P;
struct Tag {
    int mul, add;
    Tag(int _mul = 1, int _add = 0): mul(_mul), add(_add) {} // 乘法默认 1，加默认 0
    void apply(Tag t) {
        mul = 1LL * mul * t.mul % P;
        add = (1LL * add * t.mul + t.add) % P;
    }
};
struct Info {
    int sum = 0;
    void apply(Tag t, int len) {
        sum = (1LL * sum * t.mul + 1LL * t.add * len) % P;
    }
};
Info operator+(Info a, Info b) {
    Info c;
    c.sum = (a.sum + b.sum) % P;
    return c;
}

完整代码

#include <bits/stdc++.h>

using LL = long long;

template<class Info, class Tag>
struct LSGT {
    #define l(p) (p << 1)
    #define r(p) (p << 1 | 1)
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LSGT() {}
    LSGT(int _n, Info _v = Info()) {
        init(_n, _v);
    }
    template<class T>
    LSGT(std::vector<T> _init) {
        init(_init);
    }
    void init(int _n, Info _v = Info()) {
        init(std::vector(_n, _v));
    }
    template<class T>
    void init(std::vector<T> _init) {
        n = _init.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        auto build = [&](auto self, int p, int l, int r) {
            if (r - l == 1) {
                info[p] = _init[l];
                return;
            }
            int m = l + r >> 1;
            self(self, l(p), l, m);
            self(self, r(p), m, r);
            pull(p);
        };
        build(build, 1, 0, n);
    }
    void pull(int p) {
        info[p] = info[l(p)] + info[r(p)];
    }
    void apply(int p, const Tag &v, int len) {
        info[p].apply(v, len);
        tag[p].apply(v);
    }
    void push(int p, int len) {
        apply(l(p), tag[p], len / 2);
        apply(r(p), tag[p], len - len / 2);
        tag[p] = Tag();
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = l + r >> 1;
        push(p, r - l);
        if (x < m) {
            modify(l(p), l, m, x, v);
        } else {
            modify(r(p), m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info query(int p, int l, int r, int x, int y) {
        if (l >= y or r <= x) {
            return Info();
        }
        if (l >= x and r <= y) {
            return info[p];
        }
        int m = l + r >> 1;
        push(p, r - l);
        return query(l(p), l, m, x, y) + query(r(p), m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    void Apply(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y or r <= x) {
            return;
        }
        if (l >= x and r <= y) {
            apply(p, v, r - l);
            return;
        }
        int m = l + r >> 1;
        push(p, r - l);
        Apply(l(p), l, m, x, y, v);
        Apply(r(p), m, r, x, y, v);
        pull(p);
    }
    void Apply(int l, int r, const Tag &v) {
        return Apply(1, 0, n, l, r, v);
    }
    #undef l(p)
    #undef r(p)
};

int P;
struct Tag {
    int mul, add;
    Tag(int _mul = 1, int _add = 0): mul(_mul), add(_add) {}
    void apply(Tag t) {
        mul = 1LL * mul * t.mul % P;
        add = (1LL * add * t.mul + t.add) % P;
    }
};
struct Info {
    int sum = 0;
    void apply(Tag t, int len) {
        sum = (1LL * sum * t.mul + 1LL * t.add * len) % P;
    }
};
Info operator+(Info a, Info b) {
    Info c;
    c.sum = (a.sum + b.sum) % P;
    return c;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    std::cin >> n >> P;

    std::vector<Info> a(n);
    for (int i = 0; i < n; i += 1) {
        std::cin >> a[i].sum;
    }
    LSGT<Info, Tag> sgt(a);

    int m;
    std::cin >> m;
    while (m -- ) {
        int t, l, r;
        std::cin >> t >> l >> r;
        l -= 1;
        if (t == 1) {
            int c;
            std::cin >> c;
            sgt.Apply(l, r, Tag(c, 0));
        } else if (t == 2) {
            int c;
            std::cin >> c;
            sgt.Apply(l, r, Tag(1, c));
        } else {
            std::cout << sgt.query(l, r).sum << "\n";
        }
    }

    return 0;
}