[学习][poj3264]稀疏表（ST表） Balanced Lineup

稀疏表（ST表）的简介
稀疏表(Sparse Table, ST 表)与线段树、树状数组一样，也是常用来处理序列上的区间询问问题的。但 ST 表只能处理区间最值，即RMQ（Range Minimum Query）问题，它的空间需求也比前两者要大，是O(nlogn)级别的。ST 表需要O(nlogn)的时间预处理，并且能O(1)回答单次区间最值的询问，但不支持修改操作。因此它适用于无修改且询问次数较多的 RMQ 问题。

稀疏表（ST表）的实现
ST 表在预处理阶段需要计算一个数组f[i][j]表示区间[i,i+2j-1]的最小值，也就是从i 开始连续2j个数的最小值。它可以通过倍增得到：（将2j从中间平均分成两部分，每一部分都刚好是2j−1，而这就是一个子问题了）

显然需要计算的j的大小只有logn，因此预处理 f 的时空复杂度均为O(nlogn)。

现在考虑一个询问区间[x,y]内最小值的询问操作。
首先我们可以求出满足2i≤y-x+1≤2i+1的i ，即⌊log2(y−x+1)⌋，这样我们可以用两个长度为2i的小区间覆盖询问的大区间，如下图：

而长度为2i的区间最小值我们在预处理阶段就已求出，因此区间[x,y]的最小值等于min{f[x][i],f[y−2i+1][i]}。尽管这两个区间有交集，但对于最值来说并没有影响，这也就是ST表只适用于最值这类问题的原因。
求解⌊log2(y−x+1)⌋时不要使用语言数学库里的log函数，因为通常速度都较慢。使用 ST表时n的大小不会太大，最多只有106级别，因此可以利用位运算预处理出n以内所有数的log大小，这样就能做到O(1)的询问复杂度。

例题
题目背景
poj3264

题目描述
For the daily milking, Farmer John’s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.

Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.

题目大意
有一些牛（1——N），每头牛有不同的身高，求一些区间内牛的最大身高差（数据范围在英文里）。

输入格式
第1行：两个用空格隔开的整数，N和Q。
第2-(N+1)行：i+1行包含一个整数表示牛的高度。
第(N+2)-(N+Q+1)行：每行两个整数A和B（1≤A≤B≤n），代表查询A到B奶牛区间的最大身高差。

输出格式
每行一个整数，代表每组询问的答案。

样例数据
输入

6 3
1
7
3
4
2
5
1 5
4 6
2 2

输出

6
3
0

分析：稀疏表（ST表）模板

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<iomanip>
#include<queue>
#include<set>
using namespace std;

const int maxn=50010;
const int logn=15;
int n,m,a[maxn],minn[maxn][logn+1],maxx[maxn][logn+1];
int logg[maxn],l,r;

int main()
{
    freopen("ST.in","r",stdin);
    freopen("ST.out","w",stdout);

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);

    logg[0]=-1;
    for(int i=1;i<=n;++i)
    {
        minn[i][0]=maxx[i][0]=a[i];
        logg[i]=logg[i>>1]+1;//手算log更快
    }

    for(int j=1;j<=logn;++j)
        for(int i=1;i+(1<<j)-1<=n;++i)
        {
            minn[i][j]=min(minn[i][j-1],minn[i+(1<<(j-1))][j-1]);
            maxx[i][j]=max(maxx[i][j-1],maxx[i+(1<<(j-1))][j-1]);   
        }

    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&l,&r);
        int k=logg[r-l+1];
        int maxans=max(maxx[l][k],maxx[r-(1<<k)+1][k]);
        int minans=min(minn[l][k],minn[r-(1<<k)+1][k]);
        int ans=maxans-minans;
        printf("%d\n",ans);
    }

    return 0;   
}

本题结。