最小白的RMQ，求第i到第j的最大值和最小值差值。采用SparseTable算法，其实就是一种相当高效的打表，空间范围nlogn，每次查询的时间只需要常数。

假如是一般的打表，对每组i和j，记录下第i到第j的最大值和最小值，需要的空间为N²，N增大时显然无法满足要求。因此考虑改进算法，适当扩大时间，缩小空间，使之平衡。

ST采用的方法相当高效，二分划分，把每个i的所辖范围划分成1，2，4，8，16的小块，和操作系统中伙伴系统的划分倒有几分类似。

以最大值为例。F(i,j)表示以i位元素开始，连续2ⁱ个元素中的最大值。初值设所有的F(i,0)即为i的值。

那么，F[i,j]=max（F[i，j-1],F[i+2^(j-1)，j-1]）。这个等式不难推出。

然后计算l和r区间最大值时，只要划分成两块小且互相覆盖的区间就可以了。

第一次做的时候计算最后区间出了点差错，百思不得其解。为什么是(ln(r-l+1)/ln(2))；r-l计算莫非会出精度错误？

#include <cstdio>
#include <cmath>
#include <string>

int N, Q, a[50000], s[16][50000], t[16][50000], A, B, L;

#define max( x, y ) ( (x) > (y) ? (x) : (y) )
#define min( x, y ) ( (x) < (y) ? (x) : (y) )

void pt ()
{
    int i, j;
    for ( i = 0; i <= L; i ++ )
    {
        for ( j = 0; j < N; j ++ )
        {
            printf ( "%d ", t[i][j] );
        }
        printf ( "\n" );
    }
}

void init ()
{
    memset ( s, 0, sizeof ( s ) );
    memset ( t, 0, sizeof ( t ) );
    scanf ( "%d %d", &N, &Q );
    int i, j;
    L = log ( double ( N ) ) / log ( 2.0 );
 printf ( "%d\n", L );
    for ( i = 0; i < N; i ++ )
    {
        scanf ( "%d", &a[i] );
    }
    for ( j = 0; j < N; j ++ )
    {
        s[0][j] = t[0][j] = a[j];
    }
    for ( i = 1; i <= L; i ++ )
    {
        for ( j = 0; j < N; j ++ )
        {
            int j1 = j + ( 1 << ( i - 1 ) );
            if ( j1 < N )
            {
                s[i][j] = min ( s[i - 1][j], s[i - 1][j1] );
                t[i][j] = max ( t[i - 1][j], t[i - 1][j1] );
            }
            else
            {
                s[i][j] = s[i - 1][j];
                t[i][j] = t[i - 1][j];
            }
        }
    }
    //pt ();
}

int rmq ( int l, int r )
{
    int m = ( log ( double ( r - l + 1 ) ) / log ( 2.0 ) );
 int l0 = l, r0 = r - ( 1 << m ) + 1;
 //printf ( "%d %d %d\n", m, l0, r0 );
 int mx = max ( t[m][l0], t[m][r0] );
 int mn = min ( s[m][l0], s[m][r0] );
 return mx - mn;
}

void calc ()
{
    int i;
    for ( i = 0; i < Q; i ++ )
    {
        scanf ( "%d %d", &A, &B );
        A --, B --;
        if ( A == B )
        {
            printf ( "0\n" );
            continue;
        }
        printf ( "%d\n", rmq ( A, B ) );
    }
}

int main ()
{
    //freopen ( "t.txt", "r", stdin );
    init ();
    calc ();
    return 0;
}

评论