ST表

问题
    数列中下标在l ~ r之间的数最大（小）值是多少

时间复杂度
    O( 1 )

状态表示
    f[i][j]表示从 i 开始的 2^j 个数的最大值

状态转移方程
    f[i][j] = max( f[i][j - 1], f[i + 2 ^ (j - 1)][j - 1] )

初值
    f[1 ~ n][0] = a[1 ~ n]

目标
    max / min
code
    void pre()
    {
        for( int i = 1; i <= n; i ++ )
            f[i][0] = a[i];

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

    }

    int ask( int l, int r )
    {
        int k = log2( r - l + 1 );
        return max( f[l][k], f[r - ( 1 << k ) + 1][k] );
    }