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<<log_2[i]+1)==i) ++log_2[i]; } for(int i=n;i;--i){ st[i][0]=a[i]; for(int j=1;(i+(1<<j)-1)<=n;++j) st[i][j]=max(st[i][j-1],st[i+(1<<j-1)][j-1]); } } inline int ask(int l,int r){ int k=log_2[r-l+1]; return max(st[l][k],st[r-(1<<k)+1][k]); }
原文：http://www.cnblogs.com/AireenYe/p/6270518.html