【C++入門】クエリで指定されたインデックスの左側にある0と1の個数を効率的に求める方法

本記事では、与えられた配列に対するクエリ処理の問題を解説します。各クエリで指定されたインデックスについて、そのインデックスより左側（手前）に存在する「0」の個数と「1」の個数を求めるのが目的です。

問題の例

入力: arr[ ] = { 0, 1, 1, 1, 0, 0, 0, 1, 0, 0}, queries[ ] = { 2, 4, 1, 0, 5 }
出力:
query 1: zeros = 1, ones = 1
query 2: zeros = 1, ones = 3
query 3: zeros = 1, ones = 0
query 4: zeros = 0, ones = 0
query 5: zeros = 2, ones = 3

入力: arr[ ] = { 0, 0, 1, 1, 1, 0, 1, 0, 0, 1 }, queries[ ] = { 3, 2, 6 }
出力:
query 1: zeros = 2, ones = 1
query 2: zeros = 2, ones = 0
query 3: zeros = 3, ones = 3

解法のアプローチ

素朴なアプローチ（全探索）

最もシンプルな解決策は、各クエリで指定されたインデックスまで配列を先頭から走査し、要素が「0」であればゼロのカウンターを、「1」であればワンのカウンターをそれぞれ1ずつ増やしていく方法です。

実装例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int nums[] = {1, 0, 0, 1, 1, 0, 0, 1, 0, 0};
    int queries[] = { 2, 4, 1, 0, 5 };
    int qsize = sizeof(queries) / sizeof(queries[0]);
    int zeros=0,ones=0;
    // 各クエリを順番に処理するループ
    for(int i = 0;i<qsize;i++){
        // 0と1の個数をカウント
        for(int j = 0;j<queries[i];j++){
            if(nums[j]==0)
                zeros++;
            else
                ones++;
        }
        cout << "\nquery " << i+1 << ": zeros = " << zeros << ",ones = " << ones;
        zeros=0;
        ones=0;
    }
    return 0;
}

出力結果

query 1: zeros = 1,ones = 1
query 2: zeros = 2,ones = 2
query 3: zeros = 0,ones = 1
query 4: zeros = 0,ones = 0
query 5: zeros = 2,ones = 3

この素朴なアプローチでは、クエリごとに毎回先頭から計算し直すため、時間計算量は O(Q × N) となります。配列やクエリの数が大きくなると非効率になる点に注意が必要です。

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

前述の方法では、新しいクエリが来るたびに毎回0番目のインデックスから0と1の個数を再計算していました。

そこで有効なのが前計算です。あらかじめ各インデックスの左側に存在する0と1の個数をすべて計算して配列に格納しておけば、クエリが来た際にはそのインデックスに対応する値を参照するだけで答えを返せます。

実装例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int nums[] = {1, 0, 0, 1, 1, 0, 0, 1, 0, 0};
    int queries[] = { 2, 4, 1, 0, 5 };
    int n = sizeof(nums) / sizeof(nums[0]);
    int arr[n][2];
    int zeros = 0, ones = 0;
    // nums 配列を走査して前計算を行う
    for (int i = 0; i < n; i++) {
        // 各インデックス時点での0と1の個数を arr に保存
        arr[i][0] = zeros;
        arr[i][1] = ones;
        // 条件に応じてカウンターを更新
        if (nums[i]==0)
            zeros++;
        else
            ones++;
    }
    int qsize = sizeof(queries) / sizeof(queries[0]);
    for (int i = 0; i < qsize; i++)
        cout << "\nquery " << i+1 << ": zeros = " << arr[queries[i]][0] << ",ones = " << arr[queries[i]][1];
    return 0;
}

出力結果

query 1: zeros = 1,ones = 1
query 2: zeros = 2,ones = 2
query 3: zeros = 0,ones = 1
query 4: zeros = 0,ones = 0
query 5: zeros = 2,ones = 3

この効率的なアプローチでは、前計算に O(N)、各クエリへの回答は O(1) で済むため、全体の時間計算量は O(N + Q) となり、大幅な高速化が実現できます。

まとめ

本記事では、与えられた配列に対する各クエリについて、指定されたインデックスの左側にある0と1の個数を返す問題を扱いました。単純な全探索によるアプローチと、前計算（累積和）を用いた効率的なアプローチの2つを解説しました。紹介したC++のコードは、C、Java、Pythonなど他のプログラミング言語でも同様のロジックで実装可能です。皆さんの学習の一助になれば幸いです。