前言
噢我的天哪倍增正在摧毁我的脑细胞。
阅读前记住：在 C++ 中表示2i2^i2i的方式为1<<i。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前置-倍增
倍增的基础思想
首先我们用惊人的注意力发现，任意一个整数都能表示成一堆222的幂表示。
比如要表示(10100)2=(20)10(10100)_2 = (20)_{10}(10100)2 =(20)10 ，可以表示为22+242^2+2^422+24。
显然对于一个数字，可以表示为以其二进制表示下为111的位数−1-1−1为指数的222的幂的和。大概就这个意思，语言系统不好
如何操作倍增
ST表会给你讲解的。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
正文-ST表篇
ST表的定义和作用
ST表是一种可以解决可重复贡献问题（如最大公约数，RMQ）的数据结构。
ST表的思想
现在有一个数组aaa，要求区间[l,r][l,r][l,r]的最大值，而且有很多区间，显然无法暴力。
建表
我们创建二维数组FFF，令Fi,jF_{i,j}Fi,j 表示以iii为起点，长度为2j2_j2j 的区间的区间最大值。
显然这个区间就是[i,i+2j−1][i,i+2^j-1][i,i+2j−1]。那么在实际操作的时候就要注意令i+2j−1≤ni+2^j-1\leq ni+2j−1≤n。
考虑初始情况，当j=0j=0j=0时这个区间只包含一个数就是aia_iai ，那么Fi,0=aiF_{i,0}=a_iFi,0 =ai 。
然后对于长度更长的区间，我们可以利用倍增思想把Fi,jF_{i,j}Fi,j 拆成两个长度折半的区间处理。
(图画的不好致歉)
显然，Fi,j=max(Fi,j−1,Fi+2j−1,j−1)F_{i,j}=max(F_{i,j-1},F_{i+2^{j-1},j-1})Fi,j =max(Fi,j−1 ,Fi+2j−1,j−1 )。
> 这就是为啥ST表只能解决可重复贡献问题，详见 OI-Wiki。
这样先遍历jjj再遍历iii，就可以建立ST表。
查询
假设我们要查询[l,r][l,r][l,r]区间内的最大值。
首先我们求出区间长度len=r−l+1len=r-l+1len=r−l+1。
然后，求出k=floor(log2len)k=floor(log_2len)k=floor(log2 len)（下取整不会写）。
显然如果区间长度刚好是222的幂，那么可以直接得到答案为Fi,kF_{i,k}Fi,k 。
但是不是呢？
这个过程我语言无法描述，看图吧。
两个区间的长度均为2k2^k2k。
注意到对两个区间取maxmaxmax的话，一定可以取到最大值。
发现对于黑色区间，其最大值为Fl,kF_{l,k}Fl,k ；
而对于蓝色区间，我们要先求出其左端点。由于蓝色区间的右端点为rrr，长度为2k2^k2k，那么蓝色区间的左端点就是r−2k+1r-2^k+1r−2k+1。
那么蓝色区间最大值就是Fr−2k+1,kF_{r-2^k+1,k}Fr−2k+1,k 。
最终答案：
max(Fl,k,Fr−2k+1,k)max(F_{l,k},F_{r-2^k+1,k}) max(Fl,k ,Fr−2k+1,k )
实现ST表
例题：洛谷 P3865 【模板】ST 表 & RMQ 问题
> M=18M=18M=18
首先是建表，按照上面的操作：
然后是操作：
完整的代码：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
加练
板子
洛谷 P2251 质量检测
洛谷-USACO P2880 [USACO07JAN] Balanced Lineup G
洛谷 P1816 忠诚
进阶
正在寻找……
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
引申-ST表求最近公共祖先（LCA）
洛谷 P3379 【模板】最近公共祖先（LCA） / ACGO A47208.最近公共祖先（LCA）
关于LCA的定义和性质请查看https://oi-wiki.org/graph/lca/。
前置知识-欧拉序
对于任意一棵树，对这棵树进行 DFS 遍历，每经过（注意，不是第一次经过）一个节点就把该节点加入到序列里，所得的序列就是欧拉序列。
对于欧拉序列，任一节点在序列中出现的次数为子树数量+1+1+1。
ST表求解LCA的原理
考虑这样的一个树：
其欧拉序为1 2 3 2 4 2 1 5 6 5 1。
同时，我们处理一下这个序中出现的点的深度（根节点深度为1）：1 2 3 2 3 2 1 2 3 2 1。
还有每个节点在序列中第一次出现的位置：1 2 3 5 8 9。
然后我们瞪眼一下，可以瞪出来区间内最浅的点就是LCA，显然可以做区间最小值ST表解。
详见代码，代码不是我写的，是老师写的，注释不是老师写的，是我写的。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
引用
所有内容来自老师的教程和 OI-Wiki。
