能否通过预处理让数组对a[i]+b[i]>N的查询快于线性时间？

先明确核心需求：给定两个同长度n的数组a、b（每个元素都≤N），要验证所有对应位置i的a[i]+b[i]≤N，目前用O(n)的线性遍历实现，问能不能通过预处理让这类查询的效率超过线性时间？

答案是可以，但得看你的查询场景（比如查询次数）和能接受的预处理时间/空间成本，下面是几种实用的思路：

1. 针对多次查询的分段极值预处理 #

如果需要用同一个a数组和大量不同的b数组做查询，或者反过来，这种方法最划算：

• 预处理a数组：先算出limit[i] = N - a[i]，然后给limit数组建一个稀疏表，能O(1)查询任意区间内的limit最小值。
• 预处理每个b数组：同样建稀疏表，能O(1)查询任意区间内的b最大值。
• 查询时：
  用分块或者二分法快速排查：比如把数组分成√n块，每块检查「该块b的最大值是否≤该块limit的最小值」。如果某块不满足，直接判定存在i使得a[i]+b[i]>N；如果所有块都满足，就说明所有位置都符合要求。
  这种查询的时间复杂度是O(√n)，比O(n)快很多，前提是预处理的成本能被多次查询分摊。

2. 针对N很小的频率计数预处理 #

如果N的数值远小于n（比如N是几十几百，n是上万），可以用频率统计的思路：

• 预处理每个a数组：记录每个位置i对应的limit[i] = N - a[i]，同时按limit值分组，统计每个limit值对应的位置集合。
• 预处理每个b数组：按b[i]的值分组，统计每个值对应的位置集合。
• 查询时：
  从v=1到N遍历b的可能取值，对每个v，检查是否存在位置i，使得b[i]=v且limit[i]<v（也就是a[i]+v>N）。只要找到任意一个这样的位置，就判定不满足；遍历完都没找到就判定满足。
  这种查询的时间是O(N)，当N<<n时，效率远高于O(n)。

3. 单次查询的情况 #

如果只是单次查询某个a和b的组合，预处理反而不划算——因为预处理本身至少需要O(n)时间，加上查询时间，总耗时比直接线性遍历还高，不如直接用O(n)的遍历搞定。

总结一下：只有当查询次数足够多，或者N远小于n时，预处理才能让查询效率超过线性时间；单次查询的话，线性遍历是最优解。

内容的提问来源于stack exchange，提问作者user200783