C++で配列の指定範囲[L, R]におけるビット単位ORクエリを高速に処理する方法

この記事では、整数の配列が与えられたとき、指定されたインデックス範囲 [L, R] 内に存在するすべての数値のビット単位OR（論理和）を求める問題を解説します。

入力: arr[] = {1, 3, 1, 2, 3, 4}, q[] = {{0, 1}, {3, 5}}
出力:
3
7
1 OR 3 = 3
2 OR 3 OR 4 = 7

入力: arr[] = {1, 2, 3, 4, 5}, q[] = {{0, 4}, {1, 3}}
出力:
7
7

まずはシンプルな全探索（ブルートフォース）から取り組み、その計算量が大きな制約に対しても通用するかを検証します。通用しない場合は、より効率的なアプローチへと最適化していきます。

全探索（ブルートフォース）によるアプローチ

この方法では、各クエリの範囲をそのまま走査し、範囲内のすべての数値のビット単位ORを順に計算して答えを出力します。

実装例

#include <bits/stdc++.h>
using namespace std;
int main() {
    int arr[] = { 7, 5, 3, 5, 2, 3 };
    int n = sizeof(arr) / sizeof(int); // 配列のサイズ
    int queries[][2] = { { 1, 3 }, { 4, 5 } }; // 与えられたクエリ
    int q = sizeof(queries) / sizeof(queries[0]); // クエリの数
    for(int i = 0; i < q; i++) { // すべてのクエリを処理
        long ans = 0;
        for(int j = queries[i][0]; j <= queries[i][1]; j++) // 範囲を走査
            ans |= arr[j]; // 答えを計算
        cout << ans << "\n";
    }
    return 0;
}

出力

7
3

このアプローチの時間計算量は O(N×Q) です。ここで N は配列のサイズ、Q はクエリの数を表します。ご覧のとおり、この計算量では要素数やクエリ数が多いケースには対応できません。そこで次に、大きな制約にも耐えられるようアプローチを最適化します。

効率的なアプローチ（ビット累積カウント）

この方法では、あらかじめ「各ビットがこれまでに何回出現したか」を表す累積カウント（プレフィックスカウント）を計算しておきます。各クエリに対しては、範囲 [L, R] 内のいずれかの数値に特定のビットが立っているかを確認し、立っていればそのビットを答えに含め、そうでなければそのビットは0のままにします。

実装例

#include <bits/stdc++.h>

using namespace std;
#define bitt 32
#define MAX (int)10e5

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] & (1LL << j);
            prefixbits[j][i] += prefixbits[j][i - 1];
        }
    }
    return;
}
int 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 != 0)
            ans = (ans | (1LL << i));
    }
    return ans;
}
int main() {
    int arr[] = {7, 5, 3, 5, 2, 3};
    int n = sizeof(arr) / sizeof(int); // 配列のサイズ
    bitcount(arr, n);
    int queries[][2] = {{1, 3}, {4, 5}}; // 与えられたクエリ
    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;
}

出力

7
3

このアプローチでは、前処理に O(32N) ＝ O(N) の時間計算量しかかからず、さらに各クエリも最大32ビット分の確認だけで済むため、事実上 O(1) で回答できます。その結果、要素数やクエリ数が非常に多いケースでも十分に高速に動作します。

コードの解説

まず、各ビット位置ごとに出現回数の累積和を計算して保存します。クエリが来たら、この累積カウントから l-1 までのカウントを差し引くことで、範囲 [l, r] 内の数値に関するビットカウントを求めます。

ビット単位ORには「ある数値の特定のビットが1であれば、他のどの数値とORを取ってもそのビットは1のまま残る」という重要な性質があります。この性質を利用し、あるビットのカウントが0でなければ、範囲内にそのビットが立っている数値が存在することを意味するため、答えの該当ビットを1に設定します。これをすべてのビットについて繰り返し、最終的な答えを出力します。

まとめ

この記事では、与えられた配列のインデックス範囲 [L, R] におけるビット単位ORを求めるクエリ問題を解決しました。単純な全探索と、ビット累積カウントを用いた効率的なアプローチの両方を、C++プログラムとともに学びました。同じロジックはC、Java、Pythonなどの他の言語でも同様に実装できます。この記事が皆さんの学習のお役に立てば幸いです。