倍增法（ST算法）

算法）"/>

倍增法（ST算法）

文章目录

• 倍增法（ST算法）
• • 1.算法描述
  • 2.模板
  • • 2.1 预处理
    • 2.2 询问
  • 3.典型例题

倍增法（ST算法）

1.算法描述

算法思想

st算法，适用于RMQ问题（区间最大值），也就是求出一个序列中，数值最大的一项。朴素做法自然是一遍扫描找最大值，但是当题目询问次数很多的时候，就很有可能超时，因此用倍增算法来进行一个优化。

以下是st算法求解RMQ问题的实现：

首先，我们用 f [ i ] [ j ] f[i][j] f[i][j]来表示在序列a中，第i位数字以后数 2 j 2^j 2j个数之中的最大值，那么就可以得到 f [ i ] [ 0 ] = a [ i ] f[i][0]=a[i] f[i][0]=a[i]。

接下来进行一个DP的过程：

for (int j = 1; j <= (log2(n)); j++)for (int i = 1; i <= n - (1 << j) + 1; i++)f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);

2.模板

2.1 预处理

// 预处理
void pre_work() {for (int i = 1; i <= n; ++i) f[i][0] = a[i];  // 处理长度为1的区间int t = log(n) / log(2) + 1;                  // 计算分段数for (