百万级布尔数组区间True值统计的查询优化方案咨询

针对你提到的10^6大小布尔数组的多区间True值统计需求，前缀和数组是最适合的优化方案，能把单次查询的时间复杂度降到O(1)，预处理仅需O(n)时间，完美适配查询重叠的场景。

实现思路 #

预先构建一个前缀和数组prefix，其中prefix[i]代表原布尔数组从索引0到i-1的True值总数（这种设计能更方便处理区间起始为0的情况）。比如：

• prefix[0] = 0（空区间的计数为0）
• prefix[1] = ArrayBool[0] ? 1 : 0
• prefix[2] = prefix[1] + (ArrayBool[1] ? 1 : 0)
  遍历原数组一次即可完成前缀和的构建。

当需要查询区间[i1, i2]（闭区间）的True总数时，直接计算prefix[i2 + 1] - prefix[i1]就能得到结果，全程O(1)操作。

示例代码 #

// 初始化布尔数组
boolean[] ArrayBool = new boolean[1000000];
for (int i = 0; i < 1000000; i++) {
    // 随机赋值True/False，用Math.random()模拟
    ArrayBool[i] = Math.random() > 0.5;
}

// 构建前缀和数组
int[] prefix = new int[ArrayBool.length + 1];
prefix[0] = 0;
for (int i = 0; i < ArrayBool.length; i++) {
    prefix[i + 1] = prefix[i] + (ArrayBool[i] ? 1 : 0);
}

// 处理多组查询
// 假设这里用循环处理查询，示例中用模拟输入演示
while (/* 还有查询需要处理 */) {
    int i1 = /* 获取起始索引 */;
    int i2 = /* 获取结束索引 */;
    
    // 计算并输出结果
    int count = prefix[i2 + 1] - prefix[i1];
    System.out.println(count);
}

其他可选方案（针对动态场景） #

如果后续需要支持布尔数组的动态修改（比如修改某个位置的True/False值），前缀和就不太适用了，此时可以选择线段树或树状数组（Fenwick Tree），它们能在O(logn)的时间内完成修改和查询操作，但实现复杂度比前缀和高一些。不过如果你的数组是静态的（构建后不再修改），前缀和是最优选择。

内容的提问来源于stack exchange，提问作者Lalit Verma