其他
一种比线段树还高效的区间算法
The following article is from 小K算法 Author 小K算法
来源丨经授权转自 小K算法(ID:xiaok365)
作者丨小K
02分析
这些数不会更改,所以每个区间的结果是不会变的,是否可以把所有的区间结果先计算出来?
03稀疏表
首先还是将区间划分成很多的小区间。那如何划分更合理?
第2章节中,我们枚举了所有的区间情况,可以看出其实有很多重复的情况,比如下面[0,3]其实可以通过[0,1]和[2,3]组合出来。
设数组为a[i],f[i][j]表示区间[i,j]的最大值。
则长度为1的区间总共有n个,f[i][i]=a[i]。
其实并不是,因为前面已经有了长度为1和2的,所以可以组合出长度为3和4的。
如果考虑为5的,那你怎么计算呢,前面的也推不出长度为5的结果啊,至少得有3个区间才能推出来。
但这里有个很明显的问题,就是我们的数组f[i,j]定义的不合理,因为里面很多的小区间没有用上,比如长度为3,5,6,7等,所以需要重新定义。
04状态压缩
设f[i,j]表示从i开始,长度为2^j的区间的最大值,即区间[i,i+2^j-1]。
05区间分解
所以这个处理和线段树的思想也类似,需要进行区间分解。不过线段树可能分解成很多个区间,而稀疏表只需要分解成2个区间就可以了。
对于任意区间[a,b],长度为b-a+1,总可以找到2个长度为2^j的区间,这2个区间组合起来可以完全覆盖[a,b],其中j的值为log(b-a+1)。
左边的区间左端点从a开始,长度为2^j,即区间[a,a+2^j-1]。右边的区间右端点从b开始,长度为2^j,即区间[b-2^j+1,b]。 则区间[a,b]的最大值就是这两个区间中更大的那个,即max(f[a,j],f[b-2^j+1,j])。
06代码实现
// 枚举区间长度,2^j<=n
for (int j = 1; (1 << j) <= n; ++j) {
// 枚举左端点i,右端点i+2^j-1<=n-1
for (int i = 0; i + (1 << j) <= n; ++i) {
high[i][j] = max(high[i][j - 1], high[i + (1 << (j - 1))][j - 1]);
low[i][j] = min(low[i][j - 1], low[i + (1 << (j - 1))][j - 1]);
}
}
}
cin >> n >> q;
for (int i = 0; i < n; ++i) {
cin >> high[i][0];
low[i][0] = high[i][0];
}
solve();
for (int i = 0; i < q; ++i) {
int a, b;
cin >> a >> b;
a--;
b--;
int j = (int) (log(b - a + 1.0) / log(2.0));
int minHeight = min(low[a][j], low[b - (1 << j) + 1][j]);
int maxHeight = max(high[a][j], high[b - (1 << j) + 1][j]);
cout << maxHeight - minHeight << endl;
}
return 0;
}
07总结
点分享
点点赞
点在看