像使用stl一样使用线段树 ——AtCoder Library(转载https://zhuanlan.zhihu.com/p/459579152）

地址：https://zhuanlan.zhihu.com/p/459579152

我这里翻译一下官方的文档。

首先需要满足几个性质。

(注意 ∗ 是个操作，不是单纯的一个乘号)

1)操作满足结合律 即 (a∗b)∗c=a∗(b∗c)
2)操作需要有个幺元（基本元/单位元） a∗e=e∗a=a

如果你有这个一个序列 S，长度为 N ，接下来的两个询问的操作的复杂度为 O(logN)

1)更新序列中的一个元素
2)计算区间的 ∗

需要注意的是，如果你的 ∗ 这个操作自带一个复杂度 O(T) ，最后的复杂度的计算要乘上他。

构造一个线段树（俗称build）

1)segtree<S, op, e> seg(int n)
2)segtree<S, op, e> seg(vector<S> v)

这里我们需要一个操作 op 和一个 幺元 e 。

1)的方法可以让我们构造一个长度为n的线段树，初始值为幺元e （下标从0开始

2)的方法可以让我们构造一个长度为v.size()的线段树，初始值为vector （下标从0开始

op函数的形式应该为 （这里S表示这个元素的类型

S op(S a, S b)

e的函数形式应该为

S e()

举个例子。

int op(int a, int b) {
    return min(a, b);
}
int e() {
    return (int)(1e9);
}
segtree<int, op, e> seg(10); 

这样我们定义了一个操作为min，幺元为 1e9 （很明显 min(x,1e9) = x ）,的长度为10的线段树，初始值为1e9。

构造（build）的复杂度为O(N)

//这样的一个线段是就是 单点修改 区间查询最小的一个线段树。

接下来介绍操作。

void seg.set(int p, S x)

将 a[p] 赋值为 x

复杂度为 o(logN)

S seg.get(int p)

返回 a[p]

复杂度为 o(1)

S seg.prod(int l, int r)

返回op(a[l], ..., a[r - 1]) 结果（注意是[L,R) 前闭后开）

复杂度o(logN）

S seg.all_prod()

返回op(a[0], ..., a[n - 1]) 。

复杂度为O(1)

这里还有一个树上二分的操作，我就讲一个吧。

1. (1)int seg.max_right<f>(int l)
2. (2)int seg.max_right<F>(int l, F f)

这里f的形式应该为

bool f(S x)

返回一个 r 满足

f(op(a[l],a[l+1],...,a[r-1])) = true,f[a[r]] = false;

举个例子。