SparseTable口胡笔记

先声明纯属口胡,借鉴于大神blog,写得很详细。

首先说一下这个sparse—table算法不能处理一些动态更新的题目(比如单点更新,区间更新之类的。但是处理静态的查询还是很给力的,毕竟预处理O(nlogn),查询是O(1)的。

预处理是通过dp解决的。我们先定义dp[i][j]数组的含义:表示从i开始的长度为2^j的区间的最大值(根据题目要求),也就是从i到i+2^j-1.然后我们可以看出dp[i][j]可以从dp[i][j-1](也就是从i到i+2^(j-1)-1这样的长度为2^(j-1)的区间)和dp[i+(1<<(j-1))][j-1](也就是从i+2^(j-1)到2^j-1这样长度为2^(j-1)的区间)中的最大值得到。

在实际写的时候第二维要放在外层,这是因为根据状态转移方程我们是通过两个2^(j-1)的长度区间得到的一个2^j的长度区间,所以必须保证j-1的情况全部算完再算j。这样的话是O(nlogn)的复杂度。

然后再说查询,对于[l,r]这样一个闭区间我们需要找到一个最小的k让它可以完全覆盖这个区间长度,也就是k=log(r-l+1),然后我们只需要比较dp[l][k]和dp[r-(1<<k)+1][k]即可。

贴一个丑陋的板子。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注