前言
> 像使用 std::vector 一样，使用「线段树」。
本文将介绍 AC(AtCoder) Library 中提供的 segtree 模版。
本文最后提供的 Segtree.cpp 对源码进行了一定的修改使得其可以单独在每一份 cpp 代码中使用。
同时由于本文的线段树的结构与常规的使用递归实现的线段树，存在很大的不同，本文介绍的线段树「无递归」，效率很高。
下文在介绍操作的使用方式的同时将会逐步剖析其源码的实现。
阅读代码实现部分需要读者对「面向对象」，「模板」，「函数指针」有一定的了解，并且需要一定的数学基础，能够理解 「函数」 和一些「代数」的知识。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
简介
本文将介绍一种高效的支持「单点修改」，「区间查询」以及「二分查找」的线段树。
这是一种用于幺半群 (S,⋅:S×S→S,e∈S)(S, \cdot: S \times S \to S, e \in S)(S,⋅:S×S→S,e∈S) 的数据结构，即满足以下性质的代数结构：
* 结合律：对于所有 a,b,c∈Sa, b, c \in Sa,b,c∈S，(a⋅b)⋅c=a⋅(b⋅c)(a \cdot b) \cdot c = a \cdot (b \cdot c)(a⋅b)⋅c=a⋅(b⋅c)
* 存在单位元 eee：使得对于所有 a∈Sa \in Sa∈S，a⋅e=e⋅a=aa \cdot e = e \cdot a = aa⋅e=e⋅a=a
给定一个长度为 NNN 的数组 AAA，它可以在 O(logN)O(\log N)O(logN) 的时间内处理以下操作。
* 更新一个元素的值
* 计算给定区间内所有元素的「积」
为了方便描述，在本文中我们假设 op 和 e 的时间复杂度为 常数。如果这些操作的时间复杂度为 O(T)\mathrm{O}(T)O(T)，那么本文中所有操作的时间复杂度将乘以 O(T)\mathrm{O}(T)O(T)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
操作
1. 构造函数
* (1)：它会创建一个长度为 n 的数组 a，所有元素都被初始化为 e()。
* (2)：它会创建一个长度为 n = v.size() 的数组 a，初始化为 v。
应定义以下内容。
* 存储的元素类型 T
* 二元操作 T op(T a, T b)
* 单位元 T e()
限制：
* 0≤n≤1080 \le n \le 10^80≤n≤108
复杂度：
* O(n)\mathrm{O}(n)O(n)
例如，对于一个值域不超过 10910^9109 的，总共有 101010 个元素的「区间最小值查询」的问题，我们可以用以下方式来定义：
原理与代码实现
本文介绍的线段树，结构基于「完全二叉树」，所有操作不采用递归实现。
令 n\tt{n}n 为线段树存储的元素的大小，size\tt{size}size 为 bit_ceil(n) 即不小于 nnn 的最小的 222 的非负整数次幂。
我们这里令 n=11\tt{n = 11}n=11，那么 size=16\tt{size = 16}size=16。创建一个大小为 size×2\tt{size \times 2}size×2 的数组 d\tt{d}d，我们将真实的数组 a\tt{a}a 中的数据存储在 d16,d17,⋯d26\tt{d_{16}, d_{17}, \cdots d_{26}}d16 ,d17 ,⋯d26 ，如下图所示。
对于数组 d\tt{d}d 保存以下数据：
1. d0\tt{d_0}d0 保存数据为单位元 eee。
2. 对于 1≤i<size\tt{1 \le i \lt size}1≤i<size 每个 di\tt{d_i}di 维护 op(d2i,d2i+1)\tt{op(d_{2i}, d_{2i + 1})}op(d2i ,d2i+1 )。
3. 对于 size≤i<size+n\tt{size \le i \lt size + n}size≤i<size+n 每个 di\tt{d_i}di 保存原数组中的元素 a0,a1,⋯ ,an−1\tt{a_0, a_1, \cdots, a_{n - 1}}a0 ,a1 ,⋯,an−1 。
4. 对于 size+n≤i<size×2\tt{size + n \le i \lt size \times 2}size+n≤i<size×2 每个 di\tt{d_i}di 保存数据为单位元 eee。
据此我们可以按照以下方式实现构造函数：
其中 update() 操作实现为：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. SET
将 a[p] 赋值为 xxx。
限制：
* 0≤p<n0 \le p \lt n0≤p<n
复杂度：
* O(logn)\mathrm{O}(\log{n})O(logn)。
原理与代码实现
由于上面完全二叉树的特殊性质，我们可以自底向上更新数组 d\tt{d}d。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. GET
返回 a[p]。
限制：
* 0≤p<n0 \le p \lt n0≤p<n
复杂度：
* O(1)\mathrm{O}(1)O(1)。
原理与代码实现
直接访问 d[p + size] 即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. PROD
返回数组区间 [l,r)[l, r)[l,r) 的「积」，即 op(a[l], ..., a[r - 1])，假定其满足幺半群的性质。
若 l=rl = rl=r，则返回 e()。
限制：0≤l≤r≤n0 \le l \le r \le n0≤l≤r≤n
复杂度：O(logn)\mathrm{O}(\log{n})O(logn)。
原理与代码实现
根据以上线段树实现，对于 d\tt{d}d 数组，我们有以下性质。
1. 数组中下标为偶数的元素必定为左儿子；
2. 除根节点以外，数组中下标为奇数的元素必定为右儿子；
3. di=op(d2i,d2i+1), 1≤i<size\tt{d_i = op(d_{2i}, d_{2i + 1}),\ 1 \le i \lt size}di =op(d2i ,d2i+1 ), 1≤i<size。
我们可以将查询拆分成若干个 di\tt{d_i}di ，我们取这些 di\tt{d_i}di 的「积」即可。
那么令 l\tt{l}l 为查询区间左端点， r\tt{r}r 为查询区间的右端点，我们以完全二叉树的视角考虑 d\tt{d}d 数组，l,r\tt{l, r}l,r 在树中对应的真实下标为 l+size,r+size\tt{l + size, r + size}l+size,r+size，但不妨我们分别将其记为 l,r\tt{l, r}l,r，称为「左」和「右」。
以树的深度考虑，从底到顶，不断缩小 l\tt{l}l 和 r\tt{r}r 的距离，不同深度选择相应的 did_idi ，直到 l≥r\tt{l \ge r}l≥r。
对于「左」，若 l\tt{l}l 为偶数，那么显然 dl\tt{d_l}dl 和 dl+1\tt{d_{l + 1}}dl+1 都处于区间查询范围内，那么我们便不需要取 dl\tt{d_l}dl ，而是直接跳到其父亲 dl2\tt{d_{\frac{l}{2}}}d2l ；若 l\tt{l}l 为奇数，那么显然 dl−1\tt{d_{l - 1}}dl−1 已经取过，或者不在范围内，我们直接取 dl\tt{d_{l}}dl ，同时为了避免重复取值，我们可以令 l←l+1l \gets l + 1l←l+1 从而使其跳过原来的父亲 dl2\tt{d_{\frac{l}{2}}}d2l 。
对于「右」，若 r\tt{r}r 为偶数，那么显然 dr−2\tt{d_{r - 2}}dr−2 和 dr−1\tt{d_{r - 1}}dr−1 都处于区间查询范围内，那么我们便不需要取 dr−1\tt{d_{r - 1}}dr−1 ，而是直接跳到其父亲 dr2\tt{d_{\frac{r}{2}}}d2r ；若 r\tt{r}r 为奇数，那么显然 dr\tt{d_r}dr 已经取过，或者不在范围内，我们直接取 dr−1\tt{d_{r - 1}}dr−1 ，同时为了避免重复取值，我们可以令 r←r−1r \gets r - 1r←r−1 从而使其跳过原来的父亲
dr2\tt{d_{\frac{r}{2}}}d2r 。
「左」和「右」每次检查完当前层的 did_idi 是否选取之后，都跳到下一层。
因此我们可以按照以下步骤来选择数组 d\tt{d}d 中的一些元素并求「积」：
1. 令当前查询区间对应的左边界为 l\tt{l}l，右边界为 r\tt{r}r，所取结果为 [l,r)\tt{[l, r)}[l,r) 内的「积」。
2. 令 l←l+size, r←r+size\tt{l \gets l + size,\ r \gets r + size}l←l+size, r←r+size。
3. 若 l\tt{l}l 为奇数则取 dl\tt{d_l}dl ，并同时另 l←l−1\tt{l \gets l - 1}l←l−1。
4. 若 r\tt{r}r 为奇数则取 dr−1\tt{d_{r - 1}}dr−1 ，并同时另 r←r−1\tt{r \gets r - 1}r←r−1。
5. 令 l←l2, r←r2\tt{l \gets \frac{l}{2},\ r \gets \frac{r}{2}}l←2l , r←2r 。
6. 重复执行步骤 3,4,53, 4, 53,4,5 直到 l≥r\tt{l \ge r}l≥r。
我们以上述 n=11\tt{n = 11}n=11 的数组 $\tt{a} $为例，若查询 [2,9)[2, 9)[2,9) 内所有元素的积。则在数组 d\tt{d}d 中选取的元素有 d9,d5,d24\tt{d_9, d_5, d_{24}}d9 ,d5 ,d24 ；我们只需要求 op(d[9], d[5], d[24]) 的结果即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. ALL_PROD
返回数组中所有元素的「积」，即 op(a[0], ..., a[n - 1])，假定其满足幺半群的性质。
若 n=0n = 0n=0，返回 e()。
复杂度：O(1)\mathrm{O}(1)O(1)。
原理与代码实现
直接访问 d[1] 即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. MAX_RIGHT
* (1)：在线段树上执行二分查找需要定义函数 bool f(T x)。
* (2)：需定义一个以 T 为参数，返回类型为 bool 的函数对象。
它返回一个满足以下两个条件的下标 r：
* r = l 或 f(op(a[l], a[l + 1], ..., a[r - 1])) = true
* r = n 或 f(op(a[l], a[l + 1], ..., a[r])) = false
如果 f 是单调的，那么这是满足 f(op(a[l], a[l + 1], ..., a[r - 1])) = true 的最大的 r。
限制：
* 如果以相同的参数调用 f，其应该返回相同的值，即 f 无副作用。
* f(e()) = true
* 0≤l≤n0 \le l \le n0≤l≤n
复杂度：
* O(logn)\mathrm{O}(\log{n})O(logn)
原理与代码实现
我们令 sm←e\tt{sm \gets e}sm←e 存储从 l\tt{l}l 开始从左到右，统计的所有元素的「积」。
与区间查询类似，我们利用完全二叉树的性质，当 l\tt{l}l 为左儿子时，让其不断向上。
若当前对应的 dl\tt{d_{l}}dl 若满足 f(op(sm,di))=False\tt{f(op(sm, d_i)) = False}f(op(sm,di ))=False，则向下查询，否则令 sm←op(sm,dl), l←l+1\tt{sm \gets op(sm, d_l),\ l \gets l + 1}sm←op(sm,dl ), l←l+1，即跳过其父亲，继续向上查询，直到某一层的最后一个元素为止；
向下查询的过程中，先查询左儿子 dl×2\tt{d_{l \times 2}}dl×2 是否满足 f(op(sm,dl×2))=True\tt{f(op(sm, d_{l \times 2})) = True}f(op(sm,dl×2 ))=True，若为真，同样取左儿子的值，即 sm←op(sm,dl×2)\tt{sm \gets op(sm, d_{l \times 2})}sm←op(sm,dl×2 )，再向下查找， 否则不取左儿子的值；重复执行，直到树的最后一层结束。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. MIN_LEFT
它返回一个满足以下两个条件的下标 l：
* l = r 或 f(op(a[l], a[l + 1], ..., a[r - 1])) = true
* l = 0 或 f(op(a[l - 1], a[l], ..., a[r - 1])) = false
如果 f 是单调的，那么这是满足 f(op(a[l], a[l + 1], ..., a[r - 1])) = true 的最小的 l。
限制：
* 如果以相同的参数调用 f，其应该返回相同的值，即 f 无副作用。
* f(e()) = true
* 0≤r≤n0 \le r \le n0≤r≤n
复杂度：
* O(logn)\mathrm{O}(\log{n})O(logn)
原理与代码实现
与 max_right 操作类似，先令 r←r−1\tt{r \gets r - 1}r←r−1，然后令 sm←e\tt{sm \gets e}sm←e 存储从 r\tt{r}r 开始从右到左，统计的所有元素的「积」。
再利用完全二叉树的性质，当 r\tt{r}r 为右儿子时且不为根时，让其不断向上。
若当前对应的 dr\tt{d_{r}}dr 满足 f(op(dr,sm))=False\tt{f(op(d_r, sm)) = False}f(op(dr ,sm))=False，则向下查询，否则令 sm←op(dr,sm)\tt{sm \gets op(d_r, sm)}sm←op(dr ,sm)，跳过其父亲，继续向上查询，直到某一层的第一个元素为止；
向下查询的过程中，先查询右儿子 dr×2+1\tt{d_{r \times 2 + 1}}dr×2+1 是否满足 f(op(dr×2+1,sm))=True\tt{f(op(d_{r \times 2 + 1}, sm)) = True}f(op(dr×2+1 ,sm))=True，若为真，同样取右儿子的值，即 sm←op(dr×2+1,sm)\tt{sm \gets op(d_{r \times 2 + 1}, sm)}sm←op(dr×2+1 ,sm)，再向下查找， 否则不取右儿子的值；重复执行，直到树的最后一层结束。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
SEGTREE.CPP
