专栏文章

【模板】ST表

xxxxasybt2023
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minnnkyl
此快照首次捕获于
2025/12/02 05:22
3 个月前
此快照最后确认于
2025/12/02 05:22
3 个月前
查看原文
CPP
template <typename T>
struct RMQ
{
	static const int N = 1e6+5,M = 21;
	T rmq[N][M]; int lg[N];
	inline T cmp(const T&a,const T&b) {return max(a,b);}
	void init(int n,T *a)
	{
		lg[0] = -1;
		for (int i = 1;i <= n;i ++) lg[i] = lg[i/2]+1,rmq[i][0] = a[i];
		for (int j = 1;j <= lg[n];j ++)
			for (int i = 1;i+(1<<j)-1 <= n;i ++)
				rmq[i][j] = cmp(rmq[i][j-1],rmq[i+(1<<j-1)][j-1]);
	}
	inline T query(int l,int r) {return cmp(rmq[l][lg[r-l+1]],rmq[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);}
};

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...