在由 K 个线性函数组成的数组中搜索小于 V 的最大值

Question

很抱歉问题描述不够清晰。

我有一个由长度组成的数组 $N$ 由...组成的 $K$ 线性子数组。我们将线性子数组定义为数组的连续子数组 $[l,r]$ 在哪里 $A[i]-A[i-1] = C$, ，一个常数，对于所有 $l<i<=r$. 。（笔记： $C$ 不同的子数组可能不同；数组的元素是整数。）请注意，线性子数组 不相交 （任何一对相邻的线性子数组之间都有一个元素交集）。例如，[1,3,5,4,3,2] 有两个线性子数组：[1,3,5] 和 [5,4,3,2]。[1,3,5,1,2,3] 将有三个：[1,3,5]、[5,1]、[1,2,3]。

我希望找到小于查询值的最大值的多个查询 $V$, ， 在 $o(K)$ 和 $o(N)$ 每次查询的时间，其中 $o(K^2)$ 和 $o(N)$ 预处理。（假设数组已经存储在 K 线性子数组，也许用常数表示 C 以及每个子数组的长度，并且子数组是有序的。因此，您将获得包含所有线性子数组的起点和终点的数组，以及线性常数 C, ，如前所述。因此，一开始就不需要导出线性子数组。）否则，我们将不胜感激（无论是正式的还是非正式的）证明不可能这样做的证明。

当然，平衡二叉搜索树（BBST）或者简单的排序就可以达到目的，但是需要 $O(NlogN)$ 预处理，这太多了。检查每个子数组中的最大有效值需要 $O(K)$ 每个查询，这又太多了。也许有可能将这两者结合起来吗？

随机算法是可以的，只要它们总是能获得正确的答案并且在平均情况下工作得足够快，尽管确定性算法是首选。

感谢您的所有回复。我想知道这个问题是否有任何研究？这似乎不是一个太晦涩的话题，但不幸的是我的搜索能力还不够。

编辑：一个看起来很有用的方法。

这是我提出问题后的想法；我想知道这是否会有帮助。它也使用了模的思想。初始化 V=0, ，并允许每个线性子数组存储为 L,R;在哪里 L 是子数组的最小值，并且 R 是最大值。当我们收到以下查询时 V, ，我们以某种方式排除了其中的元素 L>V 和 R<V （也许通过使用多个维度？）补充数据结构存储数组中元素的最小理论差异，类似于 L - V mod c[i]. 。所以本质上，我们现在需要能够在此数据结构上运行范围添加，但是如果任何元素的值变成 <0 或者 >=c[i] 它需要重置（例如如果一个元素在 c[i]=5 时等于 -1，它将被重置为 4；如果具有相同 c[i] 且等于 6 的元素将被重置为 1)；并且还运行范围最小查询。

如果能做出这样的数据结构，问题就解决了。麻烦在于模数，因为范围添加和范围最小查询可以使用线段树和惰性传播轻松完成；以及排除某些元素。

Answer 1

无法保证找到小于查询值的最大值 $V$ 在 $o(K)$ 预处理时间 $o(N)$ 时间。

从下面的极端情况中可以很容易地看出这一点。让 $A$ 可以是任意数组 $N$ 整数，由以下组成 $K=N-1$ 线性子数组。

• 子数组 $A[0], A[1]$ 和 $C=A[1]-A[0]$.
• 子数组 $A[1], A[2]$ 和 $C=A[2]-A[1]$.
• $\cdots$
• 子数组 $A[N-2], A[N-1]$ 和 $C=A[N-1]-A[N-2]$.

和 $o(N)$ 时间预处理和 $o(K)=o(N)$ 时间处理时，算法甚至无法读取其中的某些数字 $A$ 什么时候 $N$ 足够大。（事实上​​​​，大多数数字 $A$.) 因此，对于某些查询值 $q$, ，算法将无法识别 $q+1$ 出现在 $A$.

（上面的解释可以更加严格，例如，使用对手的形式化方法和明确定义的计算模型。）

---

看起来更有趣的问题应该是是否存在一种算法 $o(N\log N)$ 预处理和 $o(K)$ 每个查询。或者是否有算法 $o(N)$ 预处理和 $o(K)$ 每个给出的查询 $K=o(N)$. 。无论如何，这听起来像是另一个问题。