【C++】配列のインデックス範囲[L, R]におけるビットANDクエリを効率的に処理する方法

この記事では、「整数の配列と複数のクエリが与えられ、各クエリに対してインデックス範囲 [L, R] 内の要素すべてのビットごとのAND（論理積）を求める」という問題を扱います。まずは例を見てみましょう。

入力: arr[] = {1, 3, 1, 2, 32, 3, 3, 4, 4}、q[] = {{0, 1}, {3, 5}}
出力:
1        （1 AND 3 = 1）
0        （32 AND 3 AND 4 = 0）

入力: arr[] = {10, 10, 12, 16, 8}、q[] = {{0, 2}, {3, 4}}
出力:
8
0

最初にブルートフォース（総当たり）手法を適用して計算量を確認し、十分に高速でない場合は、より優れたアプローチを段階的に検討していきます。

ブルートフォース（総当たり）アプローチ

この手法では、クエリで指定された範囲を順番に走査しながらビットANDを計算し、その結果を出力します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

int main() {
    int ARR[] = { 10, 10, 12, 16, 8 };
    int n = sizeof(ARR) / sizeof(int);             // 配列のサイズ
    int queries[][2] = { {0, 2}, {3, 4} };         // 与えられたクエリ
    int q = sizeof(queries) / sizeof(queries[0]);  // クエリの数

    for (int i = 0; i < q; i++) {                  // すべてのクエリを処理
        long ans = 1LL << 32;
        ans -= 1;                                  // ans の全ビットを 1 で初期化
        for (int j = queries[i][0]; j <= queries[i][1]; j++) // 範囲を走査
            ans &= ARR[j];                         // ビットANDを計算
        cout << ans << '\n';
    }
    return 0;
}

出力

8
0

計算量の分析

このアプローチでは、各クエリについて範囲内の要素をすべて走査するため、プログラム全体の時間計算量は O(N × Q) になります。ここで N は配列のサイズ、Q はクエリの数です。この計算量では制約が大きい場合に実用的ではないため、次により高速なアプローチを考えます。

効率的なアプローチ（ビット累積和による前計算）

このアプローチでは、あらかじめ「各ビット位置ごとに、先頭から各インデックスまでの間でそのビットが1になっている要素の数」の累積和（プレフィックスカウント）を計算しておきます。これにより、指定範囲内のセットビット（1になっているビット）の寄与を調べるだけで、各クエリのビットANDを高速に求められます。

C++での実装例

#include <bits/stdc++.h>
using namespace std;

#define bitt 32
#define MAX 100000
int prefixbits[bitt][MAX];

void bitcount(int *ARR, int n) {      // 各ビットの累積出現数を前計算
    for (int j = 31; j >= 0; j--) {
        prefixbits[j][0] = ((ARR[0] >> j) & 1);
        for (int i = 1; i < n; i++) {
            prefixbits[j][i] = ((ARR[i] >> j) & 1);
            prefixbits[j][i] += prefixbits[j][i - 1];
        }
    }
}

long check(int l, int r) {            // クエリに対する答えを計算
    long ans = 0;                     // オーバーフロー防止のため long 型を使用
    for (int i = 0; i < 32; i++) {
        int x;
        if (l == 0)
            x = prefixbits[i][r];
        else
            x = prefixbits[i][r] - prefixbits[i][l - 1];
        if (x == r - l + 1)           // 範囲内の全要素がそのビットを持つ場合
            ans |= 1LL << i;          // 結果の該当ビットを立てる
    }
    return ans;
}

int main() {
    int ARR[] = { 10, 10, 12, 16, 8 };
    int n = sizeof(ARR) / sizeof(int);            // 配列のサイズ
    memset(prefixbits, 0, sizeof(prefixbits));    // 全要素を 0 で初期化
    bitcount(ARR, n);

    int queries[][2] = { {0, 2}, {3, 4} };        // 与えられたクエリ
    int q = sizeof(queries) / sizeof(queries[0]); // クエリの数
    for (int i = 0; i < q; i++)
        cout << check(queries[i][0], queries[i][1]) << '\n';
    return 0;
}

出力

8
0

コードの解説

このアプローチでは、まずすべてのビット位置について累積出現数を計算し、配列に格納します。クエリを処理するときは、あるビットについて範囲 [L, R] 内にそのビットが立っている要素の数が、範囲の要素数（R − L + 1）と一致するかどうかを確認するだけです。一致すれば範囲内のすべての要素でそのビットが1であることを意味するため、結果の該当ビットを1に設定します。逆に、範囲内に1つでもそのビットが0の要素が存在すれば、その桁のビットANDは必ず0になるためです。

これにより、前計算後は各クエリを32ビット分のループのみで処理できる、すなわちクエリあたり実質O(1)となり、全体の時間計算量は O(N × Q) から O(N + 32Q) へと大幅に改善されます。このプログラムは、制約が大きいケースでも問題なく動作します。

まとめ

この記事では、配列のインデックス範囲 [L, R] におけるビットANDを求めるクエリ処理の問題を解きました。シンプルな総当たり法と、ビット累積和を用いた効率的なアプローチの2通りの解法を、実際に動作するC++プログラムとともに学びました。同じロジックは C、Java、Python など他の言語でも同様に実装できます。本記事が皆さんのお役に立てば幸いです。