c++ - 回答二进制数组的查询

Question

给定一个长度<=10^5的二进制数组和几乎相等数量的查询。每个查询由两个整数(l,r)给出，对于每个查询，我们必须计算[l,r]范围内连续0和1的总数。

如果n是数组的长度，则1 <= l < r <= n。

例如：

如果二进制数组（1索引）是“ 011000 ”并且说有5个查询：

1 3
5 6
1 5
3 6
3 4

那么所需的答案是

1
1
2
2
0

我知道这可以通过每个查询的线性时间（最坏情况）算法来解决，但由于查询数量众多，这是不可行的。

只是想知道哪种方法是实现这一目标的最有效方法？

Answer 1

您可以使用每个查询的 O(n) 空间复杂度和 O(log(n)) 搜索时间来做到这一点。计算大小为 1、2、4、...的窗口的计数。对于给定的查询，您可以找到 O(log(n)) 个窗口（最多 2 个特定大小的窗口），求和您可以找到答案.

Answer 2

正如 Dukeling 在评论中所说，您可以在 O(n) 中进行预处理以计算数组 B，其中 B[x] 包含在 [1..r] 中看到的连续数字的总数。

这允许 O(1) 中的查询通过使用数组计算范围 [1,r] 中的总数并减去范围 [1, ,l]。

Python代码：

def preprocess(A):
    last=A[0]
    B=[0,0]
    num_consecutive=0
    for a in A[1:]:
        if a==last:
            num_consecutive+=1
        B.append(num_consecutive)
        last=a
    return B

def query(B,l,r):
    return B[r]-B[l]

A=[0,1,1,0,0,0]
B=preprocess(A)

print query(B,1,3)
print query(B,5,6)
print query(B,1,5)
print query(B,3,6)
print query(B,3,4)