c++ - 二叉索引树应用于按位与

Question

我想知道是否可以使用二叉索引树(BIT)来实现按位与(而不是通常使用范围求和)的范围查询？

这是我的更新部分代码:

memset(BIT,1<<20-1,sizeof(BIT));
void update(int idx){
    while(idx<=n){
        BIT[idx] &= a[idx];
        idx += idx&(-idx);
    }
}

有人可以告诉我是否可以编写查询部分的代码吗？据我所知，范围总和查询类似于:

int query(int idx){
    int res = 0;
    while (idx){
        res += BIT[idx];
        idx -= idx&(-idx);
    }
    return res;
}

而要查询[a,b]的总和，答案是query(b)-query(a-1)。如何将其修改为按位 AND 范围查询？

Answer 1

这是不可能的(至少只使用一个 BIT)。原因很简单:如果您知道前缀 a - 1 和前缀 b 的按位与，则不可能唯一确定 [a 的按位与, b] 范围。例如，如果 query(0) 是 1 并且 query(1) 是 1，则 的答案code>query(1, 1)(即索引为1的元素)可以是任何不能被2整除的数字。

我建议改用线段树。