[Note] 倍增策略

[L4] 倍增策略

1. 生态位

• 倍增 是基于二进制拆解的策略 —— 任何正整数都可唯一分解为若干个 $2^k$ 之和。

• 地位：分解问题的一种思维方式。

• 用途：用于解决 RMQ 问题的 ST 表，以及树上倍增 LCA 和 后缀数组 SA 等高级数据结构的基础。

• 识别：

  1. 静态区间查询：数组内容不发生修改。

  2. 幂等律：维护的信息满足 $f( a, a ) = a$（如 $Max, Min, GCD$）。

  3. 多次查询：询问次数极大（如 $10^6$），要求 $O( 1 )$ 时间内给出结果。

2. 逻辑支点

2.1 核心原理：倍增

• 状态定义: 设 $f[i][ j ]$ 表示以索引 $i$ 为起点，长度为 $2^j$ 的区间内的最值。

• 转移方程: $f[i][ j ] = \max( f[i][ j - 1 ], f[ i + 2^{j - 1} ][ j - 1 ] )$

• 原理：一个 $2^j$ 的区间可以完美拆分为两个长度相等的 $2^{j - 1}$ 区间。

2.2 幂等律

幂等律：与自身做运算，结果仍是自身。

• 原理：两个区间的重叠不会影响结果。

• $O(1)$ 策略: 对于长度为 $Len = R - L + 1$ 的查询区间，取 $k = \lfloor \log_2 Len \rfloor$。

• 物理意义: 我们可以使用两个长度为 $2^k$ 的区间（一个靠左起点 $L$，一个靠右终点 $R$）实现对全区间的重叠全覆盖。

2.3 跳转逻辑

• 当运算不满足幂等性（如区间和）但满足结合律时，ST 表退化为倍增跳转。
• 通过二进制拆分跳步，实现 $O( \log N )$ 的跳转（如 LCA 寻找祖先）。

3. 实战部署

▶

ST 表维护 Max

const int maxn = 1e5 + 50;
const int maxlg = 21;

int st[maxn][maxlg];
int lg2[maxn];
int a[maxn];


void build( int n )
{
    // 1. 递推预处理 log 数组，规避数学库 log() 的性能开销
    lg2[1] = 0;
    for( int i = 2; i <= n; ++ i ) 
    {
        lg2[i] = lg2[i >> 1] + 1;
    }

    // 2. 初始状态：长度为 2^0 = 1 的区间即元素本身
    for( int i = 1; i <= n; ++ i ) 
    {
        st[i][0] = a[i];
    }

    // 3. 倍增递推：先枚举长度指数 j，再枚举起点 i
    for( int j = 1; j < maxlg; ++ j )
    {
        for( int i = 1; i + ( 1 << j ) - 1 <= n; ++ i )
        {
            st[i][j] = max( st[i][j-1], st[i + ( 1 << (j - 1) )][j - 1] );
        }
    }
}

int query( int l, int r )
{
    // 计算满足 2^k <= Len 的最大 k
    int k = lg2[ r - l + 1 ];
    // 两区间重叠覆盖取最值
    return max( st[l][k], st[r - ( 1 << k ) + 1][k] );
}

4. 知识关联

• 关联笔记:

  • 线段树基础理论: 当区间涉及修改（动态 RMQ）时，作为 ST 表的替代方案。

  • LCA 体系: 倍增思想在树空间维度的延伸应用。