ST表的使用范围：
1.处理静态数组的极值问题
2.尾部增减数组的极值问题
ST表的原理：
1.预处理：ST表的中心思想是动态规划，我们规定数组 Max[i][j] 储存的是数组中从第 i 个元素开始，总共 2^j 个数字的极（大）值，区间末尾位置为 i+2^j-1。输入数组时，直接输入到 Max[i][0] 上。输入完成后，花费 O(nlogn) 来对 Max 数组中的所有值进行处理。有如下状态转移方程：
Max[i][j] = max( Max[i][j-1] , Max[i+(1<<(j-1))][j-1] );
2.查询：对于输入的边界 left 和 right， 我们令 d = floor(log2(right - left)) ，即使 2^d 成为能够被 [left, right] 覆盖的最大的 d 值。在求得d值之后，我们查询两个区间的最值：[left, left + 2^d] 和 [right - 2^d +1, right]；由 d 的条件可得，这两个区间都在[left, right]上，且两个区间之和就是之前的大区间。
ST表基本操作：
#define rep(i,n) for(int i = 1; i <= n; i++) //简写for循环
class STtable{
private:
int Max[Size][31];
int length;
public:
void read(int n);//输入数组
void init();//初始化处理
int find(int l, int r);//查询结果
};
输入数组
void read(int n)
{
length = n;
rep(i, n)
cin>>Max[i][0];
}
初始化处理
void init()
{
rep(j, 31)
rep(i, n - (1 << (j - 1)))
Max[i][j] = max(Max[i][j-1], Max[i+(1<<(j-1))][j-1]);
}
查询结果
#include <cmath>
int find(int l, int r)
{
if(l == r)
return Max[l][0];//特殊处理，防止log0的出现
int d = log2(r - l);
return max(Max[l][d], Max[r - (1<<d) + 1][d]);
}
尾部可增减ST表
1.增加：ST表在完成预处理后是不能直接更改原数组的数值的，不具备可维护性，但是，如果我们只对数组的尾部进行操作，可以发现新增队尾元素后，原先ST表已经维护的部分不会改变，而且需要改变的部分只需要花费 O(logn) 时间即可。
2.减少：ST表是不能随便增减元素的，但如果只是减少最后个元素，只需要让动态数组长度减少1即可。只需要在查询的过程中添加一个是否越界的条件。
对单独一个元素进行增减操作是不会出现问题的，若是先减后增，则将之前减去的部分覆盖掉即可，通过12两个操作，能确保动态数组长度范围内的查询值都是正确的即可。
代码：
#define rep(i,n) for(int i = 1; i <= n; i++) //简写for循环
class STtable{
private:
int Max[Size][31];
int length;
public:
void add(int n);//末尾增加元素
void del();//末尾删除元素
int find(int l, int r);//查询结果
};
末尾增加元素
void add(int n)
{
length++;
Max[length][0] = n;
for(int i = 1; n - (1 << i) + 1 >= 1; i++)
Max[length - (1 << i) + 1][i] = max(Max[length - (1 << i) + 1][i-1], Max[length - (1 << (i-1)) + 1][i-1]);
}
末尾删除元素
void del()
{
length--;//真就这么简单（）
}