给定一个长度<=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
我知道这可以通过每个查询的线性时间(最坏情况)算法来解决,但由于查询数量众多,这是不可行的。
只是想知道哪种方法是实现这一目标的最有效方法?