给定一个长度为 n 数组求子区间的and和为0的个数

算法1：

暴力枚举法

• 遍历所有的子区间，统计其中and和为0的子区间的个数。

时间复杂度：$O(n^3)$。

C++ 代码

算法2：

前缀和+哈希表法

• 用前缀和的思想，计算出数组的前缀and值。
• 枚举所有的子区间，计算出区间and值，如果为0，则计数器加1。
• 使用哈希表（unordered_map）来记录每个前缀and值出现的次数，对于每个子区间，用前缀and值的异或值来判断其中and和是否为0。

时间复杂度：$O(n\log n)$。

C++ 代码

算法3：

前缀和+二分查找法

• 用前缀和的思想，计算出数组的前缀and值。
• 枚举所有的子区间，计算出区间and值，如果为0，则计数器加1。
• 使用二分查找来判断区间and值是否为0，具体地，对于每个子区间，二分查找该区间最小的前缀and值和最大的前缀and值，如果两者的异或值为0，则计数器加1。

时间复杂度：$O(n\log^2 n)$。

C++ 代码