C++で解く：範囲内のK番目のビットがセットされた配列要素の数を求めるクエリ処理

はじめに

本記事では、指定された範囲内に存在する要素のうち、K番目のビットがセット（1）になっている要素の個数を求める問題について解説します。まずは具体例を見てみましょう。

入力 : arr[] = { 4, 5, 7, 2 }
クエリ1: L = 2, R = 4, K = 4
クエリ2: L = 3, R = 5, K = 1
出力 :
    0
    1

まずは総当たり（ブルートフォース）のアプローチでこの問題を解き、その手法が大きな制約値に対しても実用的かどうかを確認します。もし不十分であれば、より効率的な新しいアプローチを検討していきます。

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

このアプローチでは、単純に範囲内を走査し、各要素についてK番目のビットがセットされているかどうかを1つずつ確認します。セットされていればカウントを増やし、最終的なカウントを答えとして返します。

コード例

#include<bits/stdc++.h>
using namespace std;
#define MAX_BITS 32
bool Kset(int n, int k) { // k番目のビットがセットされているか確認
    if (n & (1 << (k - 1)))
        return true;
    return false;
}
int query(int L, int R, int K, int arr[]) {
    int count = 0; // 範囲内の該当数を数えるカウンター
    for (int i = L; i <= R; i++) { // 範囲を走査
        if (Kset(arr[i], K)) {
            count++;
        }
    }
    return count;
}
int main() {
    int arr[] = { 4, 5, 7, 2 }; // 与えられた配列
    int n = sizeof(arr) / sizeof(arr[0]); // 配列のサイズ
    int queries[][3] = { // 与えられたL、R、k
        { 2, 4, 4 },
        { 3, 5, 1 }
    };
    int q = sizeof(queries) / sizeof(queries[0]); // クエリの数

    for (int i = 0; i < q; i++) {
        int L = queries[i][0] - 1;
        int R = queries[i][1] - 1;
        int K = queries[i][2];

        cout << query(L, R, K, arr) << "\n";
    }
    return 0;
}

出力

0
1

上記のアプローチの計算量はO(N×Q)です。ここでNは配列のサイズ、Qはクエリの数を表します。ご覧のとおり、制約が大きくなると処理時間が膨大になるため、この手法は大規模な入力には不向きです。そこで次に、より効率的なアプローチによるプログラムを作成しましょう。

効率的なアプローチ

このアプローチでは、各インデックスまでに出現した各ビットの累積カウントを記録する2次元の累積和（プレフィックスサム）配列を事前に構築します。これにより、各クエリの答えをO(1)の計算量で求めることが可能になります。

コード例

#include<bits/stdc++.h>
using namespace std;
#define bits 32 // ビット数

int P[100000][bits+1];

bool Kset(int n, int k) {
    if (n & (1 << (k - 1)))
        return true;
    return false;
}
void prefixArray(int n, int arr[]) { // 累積和配列の構築
    for (int i = 0; i <= bits; i++) {
        P[0][i] = 0; // すべてのビットの初期カウントを0に設定
    }
    for (int i = 0; i < n; i++) {
        for (int j = 1; j <= bits; j++) {
            bool flag = Kset(arr[i], j);
            if (i) // 前のインデックスのカウントを引き継ぐ
                 P[i][j] = P[i - 1][j];
            if (flag) { // j番目のビットがセットされていればカウントを増やす
                 P[i][j]++;
            }
        }
    }
}
int query(int L, int R, int K) {
    if (L) // Lが0でない場合、Rまでの累積和からL-1までの累積和を引いて返す
        return P[R][K] - P[L - 1][K];
    else
        return P[R][K];
}
int main() {
    int arr[] = { 8, 9, 1, 3 }; // 与えられた配列
    int n = sizeof(arr) / sizeof(arr[0]); // 配列のサイズ
    int queries[][3] = {
        { 1, 3, 4 },
        { 2, 4, 1 }
    };
    prefixArray(n, arr); // 累積和配列を作成する関数を呼び出す
    int q = sizeof(queries) / sizeof(queries[0]); // クエリの数

    for (int i = 0; i < q; i++) {
        int L = queries[i][0] - 1;
        int R = queries[i][1] - 1;
        int K = queries[i][2];
        cout << query(L, R, K) << "\n";
    }
    return 0;
}

出力

2
3

累積和配列を管理することで、各クエリへの回答をO(1)で求められるようになります。その結果、全体の計算量は前処理を含めてO(N)（Nは与えられた配列のサイズ）まで大幅に削減されます。

コードの解説

このプログラムでは、配列の各インデックスに対して「その位置までに出現した各ビットの累積カウント」を保持するテーブルを構築しています。まず配列全体を一度走査してこの累積カウントを作成します。準備が完了すれば、任意の範囲におけるK番目のビットの出現回数は、「R番目までのK番目ビットの累積カウント」から「L-1番目までのK番目ビットの累積カウント」を引くだけで即座に求められます。これがまさに求める答えです。

まとめ

本記事では、「範囲内でK番目のビットがセットされている配列要素の数を求めるクエリ」という問題を取り上げました。ブルートフォース法と2次元累積和を用いた効率的な手法の両方を実装し、計算量の違いも確認しました。同じロジックはC、Java、Pythonなど他の言語でも同様に実装できます。本記事が皆様の学習のお役に立てば幸いです。