Atcoder 的 AC Library 中封装了线段树模板，在需要构建线段树的时候，需要像使用 STL 标准库那样引入即可。注意是如何实例化的，下面通过几个例子来说明

部分方法和单点修改一样
不动脑子地写线段树——单点修改

源码链接

线段树区间修改

线段树区间修改同样是针对单群而言的，这里引入一个映射集 $F$
满足 $(F:S \to S, \quad S \times S \to S, \quad e\in S)$

• $F$ 中存在一个恒等映射 $id(x)$，满足对于所有 $x \in S$，$id(x) = x$ 成立

• 满足闭包，即对于 $f, g \in F$，那么 $g \circ f \in F$

• 积性，对于操作 *（我们之前用 op 定义了），对于 $x, y \in S$，
  $$f(x \* y) = f(x) * f(y)$$

线段树区间修改可以执行以下操作

• 求一个区间 $[l, r]$ 中 $op(a_l, \cdots, a_r)$ 的结果

• 对区间 $[l, r]$ 中所有元素 $x$ 执行映射 $x \to f(x), f \in F$

构造函数和方法

(1) lazy_segtree<S, op, e, F, mapping, composition, id> seg(int n);
(2) lazy_segtree<S, op, e, F, mapping, composition, id> seg(vector<T> v);

• S, op, e 和单点修改的一样
  S 表示节点元素类型，op对应pull操作，e是幺元

• F是映射的类型，比如让区间都加上一个数，F <=> long long
  因为 long long add 即可表示区间加运算
  如果涉及两种操作，比如区间加，区间乘，那么F可以定义为一个结构体
  struct F { long long mul, add; };

• mapping 是映射规则，形式为 S mapping(F f, S x)，返回 $f(x)$
  值得注意的是，这里的F f表示什么？
  可以理解为f是线段树懒标记，可以是 add, mul,... 等等
  F 为懒标记的类型，比如让区间所有数都+d，d是一个long long型
  那么就可以如下声明（参数f可以理解为tag）

对于 $x$ 节点表示的区间，$x \to f(x)$

// 仅执行区间加法
struct S {
 long long sum, len;
};
S mapping(long long f, S x) {
 return S{x.sum + f*x.len, x.len};
}

容易看出，mapping实际上规定了一个区间怎么打懒标记

• composition 规定了 $f\circ g$ 的规则
  假设只有一种操作，比如就是区间加，考虑 F composition(F f1, F f2)
  如果懒标记是long long类型的，就是 ll compositon(ll f1, ll f2)
  表示的意义是，先加上懒标记f2，再加上f1，可以如下声明

long long composition(long long f1, long long f2) {
  return f1 + f2;
}

复杂的复合操作如下，比如我们需要执行区间加和区间乘，规定

struct F {
  long long mul, add;
};
S mapping(F f, S x) {
  return S{ x.sum*f.mul + x.len*f.add, x.len };
};

说明，注意如果同时有加法和乘法两种操作
只有加法的时候，我们可以定义变换 F f(add, 1)
只有乘法的时候，类似定义变换 F f(0, mul)，这样两种操作可以统一起来

那么对于复合操作(F f, F g)，$f\circ g$ 可以如下声明

$$g(x) = x\cdot g.mul + g.add \\\ f(g(x)) = (x\cdot g.mul) \cdot f.mul + f.add$$

从而 f(g(x)) = f.mul*g.mul*x + f.mul*g.add+f.add

F composition(F f, F g) {
  return F{ f.mul*g.mul, f.mul*g.add+f.add };
}

• F id() 定义了恒等变换
  如果同时有加法和乘法两种操作，那么恒等变换就是

F id() {
  return F{ 1, 0 };
}
// x = x*1 + 0

set, get

void seg.set(int p, S x)
S seg.get(int p)

prod

S seg.prod(int l, int r)

返回 op(a[l], a[l+1], ..., a[r-1])的结果，如果 l = r 返回 e()

all_prod

S seg.all_prod()

返回 op(a[0], a[1], ..., a[n-1])的结果，n = 0 返回 e()

apply

(1) void seg.apply(int p, F f)
(2) void seg.apply(int l, int r, F f)

执行单点修改，区间修改
特别地，区间修改，对所有的 i = [l, l+1,..., r-1]
执行 $a[i] \to f(a[i])$

max_right

(1) int seg.max_right<g>(int l)
(2) int seg.max_right<G>(int l, G g)

• G 是一个函数对象，一般来说，返回的是一个bool类型
• 必须定义 bool g(S x)，并执行线段树二分
  S是线段树的节点数据类型

该函数的返回值是 r，满足
r = l（此时没找到），或者 g( op(a[l], a[l+1], ..., a[r-1]) ) = true
r = n（此时到end一整段都满足），或者 g( op(a[l], a[l+1], ..., a[r]) ) = false

min_left

(1) int seg.min_left<g>(int r)
(2) int seg.min_left<G>(int r, G g)

• 同样需要定义 bool g(S x) 来执行线段树二分
  S 是线段树节点数据类型

该函数的返回值是一个 l，满足

• l = r（此时没找到），或者 g( op(a[l], a[l+1], ..., a[r-1]) ) = true
• l = 0（此时到begin一整段都满足），或者 g( op(a[l-1], a[l], ..., a[r-1]) ) = false

区间修改的例子

给定 $a_1, a_2, \cdots, a_n$，支持 q 个操作

• 1 l r d，给区间 [l, r] 所有数加上 d
• 2 l r d，给区间 [l, r] 所有数乘上 d
• 3 l r d，给区间 [l, r] 所有数赋值为 d
• 4 l r，查询 [l, r] 区间和，并对 ${10^9+7}$ 取模

算法实现

// mint 是取模数类
struct S {
    mint sum;
    int len;
};

S op(S a, S b) {
    return S{a.sum + b.sum, a.len + b.len};
}

S e() {
    return {0, 0};
}

struct F {
    mint mul, add;
};

S mapping(F f, S x) {
    return S{ x.sum*f.mul + mint(x.len)*f.add, x.len };
}

F composition(F f, F g) {
    return F{ f.mul*g.mul, f.mul*g.add + f.add };
}

F id() {
    return F{1, 0};
}

int main() {
    // 部分代码省略
    vector<S> a(n);

    for (int i = 0; i < n; i++) {
        int x; scanf("%d", &x);
        a[i] = S{ mint(x), 1 };
    }

    lazy_segtree<S, op, e, F, mapping, composition, id> tr(a);

    while (q--) {
        // 仅以区间乘法为例子
        F f = F{mint(d), mint(0)};
        tr.apply(l, r+1, f);
    }
}