平衡的队列
寻求不固定区间内最大值和最小值的差值。
预处理以每一个位置为开头,长度为20,21,…,2log2n2^0,2^1,…,2^{log_2n}20,21,…,2log2 n的所有区间最值。
只考虑最大值,用f[i][j]f[i][j]f[i][j]表示hi,hi+1,…,hi+2j−2,hi+2j−1h_i,h_{i+1},…,h_{i+2^j-2},h_{i+2^j-1}hi ,hi+1 ,…,hi+2j−2 ,hi+2j−1 中的最大值,用递推的方式计算所有的fff,转移为:f[i][j]=max(f[i][j−1],f[i+2j−1][j−1])f[i][j]=max(f[i][j-1],f[i+2^{j-1}][j-1])f[i][j]=max(f[i][j−1],f[i+2j−1][j−1])。预处理时间复杂度O(nlog2n)O(nlog_2n)O(nlog2 n)
接下来是查询。设需要查询最大值的区间为[l,r][l,r][l,r]。记区间长度为LLL,则该区间可以拆分成O(log2L)O(log_2L)O(log2 L)的小区间。将LLL二进制拆分,从LLL开始向后跳,每次跳拆出一个2的幂的个数,就可以拼凑出整个区间。
单次查询时间复杂度O(log2n)O(log_2n)O(log2 n)。