algorithm - 最大数量的线段树查询

Question

我已经给出了一个 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 在这里不起作用。

Answer 1

让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)) .该解决方案使用线性量的空间。