ST表

给定一个数列\(a,O(nlogn)\)预处理,\(O(1)\)查询数列在区间\([l,r]\)的最值.

本文介绍求最大值.

实现

预处理

\(st[i][j]\)表示\(max\{a_k\}(k\in[i,i+2^j))\).

\(st[i][j]=\begin{cases}a_i&j=0\\max(st[i][j-1],st[i+2^{j-1}][j-1])&j>0\\\end{cases}\)

询问

询问\([l,r]\),令\(k=\lfloor\;log_2^{r-l+1}\;\rfloor\),则答案为\(max(st[l][k],st[r-2^k+1][k])\).

int st[N][K],a[N],log_2[N];
inline void ini_st(){
    log_2[1]=0;
    for(int i=2;i<=n;++i){
        log_2[i]=log_2[i-1];
        if((1<