2013-team4/code/st-table

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
静态 RMQ
预处理时间/空间复杂度 nlogn，常数查询
}}}
{{{
创建
RMQ gao;
初始化为长度为 n 的数组 arr
gao.init(arr, n);
查询 [l, r] 区间最大值（最小值将两个 max 改成 min 即可）
gao.query(l, r);
}}}
{{{
typedef int DATA;
const int MAXN = 100004, LOGN = 18;

struct RMQ{
    DATA d[MAXN][LOGN];
    void init(DATA a[], int n){
        for(int i = 0; i < n; i++) 
            d[i][0] = a[i];
        for(int j = 1, l = 2; (1 << j) <= n; j++, l <<= 1)
            for(int i = 0; i + l - 1 < n; i++)
                d[i][j] = max(d[i][j - 1], d[i + (l >> 1)][j - 1]);
    }
    DATA query(int l, int r){
        int j = 0;
        while((1 << (j + 1)) <= r - l + 1) j++;
        // j = 31 - __builtin_clz(r - l + 1)；
        return max(d[l][j], d[r - (1 << j) + 1][j]);
    }
};
}}}

静态 RMQ
预处理时间/空间复杂度 nlogn，常数查询

创建
RMQ gao;
初始化为长度为 n 的数组 arr
gao.init(arr, n);
查询 [l, r] 区间最大值（最小值将两个 max 改成 min 即可）
gao.query(l, r);

typedef int DATA;
const int MAXN = 100004, LOGN = 18;
struct RMQ{
    DATA d[MAXN][LOGN];
    void init(DATA a[], int n){
        for(int i = 0; i < n; i++) 
            d[i][0] = a[i];
        for(int j = 1, l = 2; (1 << j) <= n; j++, l <<= 1)
            for(int i = 0; i + l - 1 < n; i++)
                d[i][j] = max(d[i][j - 1], d[i + (l >> 1)][j - 1]);
    }
    DATA query(int l, int r){
        int j = 0;
        while((1 << (j + 1)) <= r - l + 1) j++;
        // j = 31 - __builtin_clz(r - l + 1)；
        return max(d[l][j], d[r - (1 << j) + 1][j]);
    }
};