count二进制数组中0个数大于1的子数组个数

Question

给定一个二进制数组。找出0大于1的子数组的个数?

我已经想出了一个朴素的O(N2)解决方案，有没有可能变得更好?

Answer 1

调用F[i]是从a[1]到a[i]的位1的个数;G[i]表示从a[1]到a[i]的0位的个数。所以我们需要找到i,j (0<=i<=n)对的个数F[j]-F[i]

可以取O(N^2)但是如果我们变换表达式

F[j] - F[i]

& lt; =比;F[j] - G[j] 如果我们调用C[i] = F[i]- G[i],所以:

(*) & lt; =比;C [j] & lt;C[我]。

问题将变成:找到iandC[i]>C [j]． 我们可以很容易地用二叉搜索树在近似O(NlogN)的情况下求解。