ST表易错处

\(updata : 2021.12.6\)

思想 : 看似有很多细节 , 但只要时刻牢记 \(f[i][j]\) 表示区间 \([i , i+(1< 即可

\(① :\) 更新\(f[i][j]\) , \(j\) 的枚举一定在外层 , 看方程转移 f[i][j] = max(f[i][j-1] , f[i + (1< , 如果 \(i\) 在外层 , \(f[i + (1< 是未知状态.


而且注意是 i + (1< , 而不是 i + 1< , 一定要打括号


\(② :\)
int t = lg[r-l+1]  而不是 int t = lg[r-l]
将 \(l = 1 , r = 4\) 代入即可验证后者是错的.

#include
#include
using namespace std;
const int N = 1e5+1;
int n,m,a[N],f[N][20],lg[N];
int main()
{
	scanf("%d%d",&n,&m);
	lg[0] = -1;
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
		f[i][0] = a[i];
		lg[i] = lg[i>>1] + 1;
	}
	for(int j=1;j<=19;++j)
		for(int i=1; i+(1<

ST表易错处

相关

标签