algorithm - 查找具有目标按位 AND 值的子数组

Question

给定一个数组 A尺寸N和一个整数 P , 找到子数组 B = A[i...j]这样 i <= j ，计算子数组元素的按位值，比如 K = B[i] & B[i + 1] & ... & B[j] .
输出|K-P|的最小值在 K 的所有可能值中.

Answer 1

这是一种拟线性方法，假设数组的元素具有恒定的位数。

矩阵 K[i,j] = A[i] & A[i + 1] & ... & A[j] 的行单调递减(忽略下三角矩阵)。这意味着 K[i,:] 和搜索参数 P 之间的差的绝对值是单峰的并且是最小值(不一定最小值因为相同的最小值可能会出现多次，但随后它们会连续出现)可以在 O(log n) 时间内用 ternary search 找到(假设访问 K 的元素可以安排在常数时间内)。对每一行重复此操作并输出最低最小值的位置，使其达到 O(n log n)。

在小于行大小的时间内执行行最小搜索需要隐式访问矩阵 K 的元素，这可以通过创建 b 来实现前缀和数组，A 元素的每一位。然后可以通过计算所有 b 单位范围和并将它们与范围的长度进行比较来找到范围与，每次比较都给出范围与的一位。这需要 O(nb) 的预处理并给出 O(b)(如此恒定，根据我在开始时所做的假设)访问 K 的任意元素。

我曾希望绝对差矩阵是允许使用 SMAWK 算法的 Monge 矩阵，但情况似乎并非如此，我找不到插入该属性的方法。