[模板]ST表

 

 模板:(以O(1)时间返回区间内最大值)

int st[100010][20];        // 20 意味着能容纳2^20个,这个值要和第一个维度也就是数据范围要相近
void ST_prework(){
    // 假设原始数据已经读入到st[i][0]中
    int t = log(n) / log(2) + 1;
    for(int j = 1; j < t; j++)
        for(int i = 1; i <= n - (1 << j) + 1; i++)
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}

int ST_query(int l, int r){        // 返回区间内的最大值
    int k = log(r - l + 1) / log(2);
    return max(st[l][k], st[r - (1 << k) + 1][k]);
}

如果把模板中的两处"max"改为"min"就可以得到以O(1)时间返回区间内最小值的模板.可以用在这题上.