arrays - 许多子数组求和查询

Question

子数组问题:给定整数数组A(只有正数)，是否存在任意长度的连续子数组，其和为S？对此的滑动窗口解决方案是 O(N)。

现在如果我们在静态数组上有很多这样的查询 S，我们可以进行预处理。我们可以计算 O(N^2) 中的所有子数组和并将它们存储在哈希表中。这也占用 O(N^2) 空间。然后我们可以在 O(1) 中处理查询，只需从哈希表中查找 S

我的问题是，是否有一些 O(N log N) 的预处理？即使这意味着将查询降低到 O(log N)。

Answer 1

is there some O(N log N) prepeprocessing?

不。

在大小为 N 的数组中有 N² 个可能的子数组。您不能在小于 O(N²) 时间。