用途

用于RMQ（最值查询）问题中，运用倍增的思想，以O()的时间复杂度预处理，再以高效的O(1)进行查询

查询最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
int dp[200010][30];
//dp[i][j]表示以i为起点，2^j为块大小的最大值（最小值同理）
auto init=[&]()->void{
    for (int i = 1; i <= n;i++)
        dp[i][0]=a[i];
    for (int j = 1; (1 << j) <= n;j++)
        for (int i = 1; i + (1 << j) - 1 <= n;i++)
            dp[i][j] = max(max[i][j - 1], max[i + (1 << (j - 1))][j - 1]);
};
auto query=[&](int l,int r)->int{
    int len=(int)(log2(r-l+1));
    return max(dp[i][1<<len],dp[i+(1<<(len-1))][len]);
};

拓展应用

ST表不仅能用于最值查询，对于满足结合律的信息都可以进行建表操作，如GCD值(查询复杂度不是O(1))等等.
代码同理.