string - 如何在二进制字符串的特定范围内找到010的数字

Question

给定一个二进制字符串。如何在字符串的特定范围内找到 "010" 的出现。
例如，我有字符串 "0100110" 。如果给定范围是 3 7(基于 1 的索引)，则输出将为 4。我找不到任何更快的方法来解决它。

在尝试这个过程中，我可以用 O(N) 的复杂度来解决它。方法是 - 首先我指出一定范围内所有 '1' 的位置，然后使用这些位置我将计算出两个后面的 '0' 的数量来回。然后将后面找到的单个'1' 的'0' 数与前面找到的'0' 数相乘。然后将一定范围内的每个'1'的相乘结果相加。

对于给定的示例，'1' 在范围内的位置是 {5, 6}。现在，对于索引 5，我前后的 '0' 数量分别为 2 和 1。所以我们可以让子序列"010"是2。类似地，对于索引 6，我们也得到答案是 2。总共我们可以使子序列 "010" 总共 4 次。

但是当我们对给定字符串进行一定范围内的Q 查询时，我的方法很容易达到时间复杂度O(N²) 。我尝试了很多但未能找到优化它的方法。任何人都可以帮助我使用低于 O(N²) 复杂度的方法吗？只是提到时间限制应该是1 秒。提供伪代码加分。

~提前致谢。

Answer 1

预处理:使辅助数组包含到给定位置的累积零数(aux[0]=0)

  0 1 0 0 1 1 0  //string
0 1 1 2 3 3 3 4  //aux array A[]

对于给定的 L..R 范围扫描，对于 1 的每个 k 索引获取范围内零的数量 - O(1) 操作

P[k] = (A[k] - A[L-1]) * (A[R] - A[k])
S = Sum(P[k], k=L..R)

所以我们每个查询的时间都是O(R-L)，Q 查询的最坏情况是O(Q*N)

但是仔细看公式:

P[k] = (A[k] - A[L-1]) * (A[R] - A[k]) = 
       A[k] * (A[R] + A[L-1]) - A[k]^2 - A[R] * A[L-1] = 
       A[k] * LRSum - A[k]^2 - LRProd
S = Sum(A[k] for ones) * LRSum - Sum(A[k]^2) - LRProd * NumOfOnes 

请注意，LRSum 和 LRProd 是给定查询的常量，我们必须计算 A[k] 的总和以及相同位置的平方和职位。似乎我们可以使用累积数组的相同想法，并在每个查询的 O(1) 中获得结果。

快速检查为您的示例提供 (3+3)*5 - (9+9) - 4*2 = 30-18-8 = 4。

使用累积数组:

  0 1 0 0 1  1  0  //string
0 1 1 2 3 3  3  4  //aux array A[]
0 0 1 1 1 4  7  7  //aux array B[]
0 0 1 1 1 10 19 19  //aux array C[]

Result = (B[R] - B[L-1]) * (A[R] + A[L-1]) - (C[R] - C[L-1]) - 
                 A[R] * A[L-1] * (R - L - 1 - (A[R] - A[L-1])) = 
         (7-1) * (4 + 1) - (19 - 1) - 4 * 1 * (7 - 2  - 4 + 1) = 4