我已经给出了一个 n 个整数的数组 A
和 X D
形式的 Q
查询,用于我必须找到的每个查询子数组中的最大元素 [Ax , A(x-D),A(x-2D)..]
例如:
A = [1,2,3,4,5,6,17,8]
we have query 7 2
Sub Array [17,5,3,1] Ans=17
由于没有更新索引,我们如何才能以比 O(Q*N)
更好的时间复杂度来解决这个问题,是否可以通过一些技术离线解决
我认为 Square Decomposition
在这里不起作用。
最佳答案
让D
大于 sqrt(N)
.那么序列 x, x - d, x - 2 * d, ... 最多包含 sqrt(N)
元素。因此,天真的解决方案适用于 O(sqrt(N))
在这种情况下,每个查询。
让D <= sqrt(N)
.最多有 sqrt(N)
如此独特 D
的。让我们遍历它们。对于固定值 d
, 我们可以计算 f[i] = max(a[i], f[i - d])
对于所有 i
在线性时间内(边界条件需要妥善处理)。所有查询的答案 (X, D)
, 其中D = d
, 就是 f[X]
.
总时间复杂度为O((N + Q) * sqrt(N))
.该解决方案使用线性量的空间。
关于algorithm - 最大数量的线段树查询,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40789321/