【C++】指定範囲内の値を持つ配列要素の個数を求めるクエリ処理の実装方法

この問題では、配列 arr[] と Q 個のクエリが与えられます。各クエリは次の2種類のいずれかです。

• {1, L, R} … 範囲 [L, R] 内の値を持つ配列要素の個数を求める

• {2, index, val} … index の位置にある要素を val に更新する

本記事では、これらのクエリを効率的に処理するC++プログラムの作成方法を、2つのアプローチに分けて解説します。

問題の例

入力:

arr[] = {1, 5, 2, 4, 2, 2, 3, 1, 3}
Q = 3
Query = { {1, 4, 8},
          {2, 6, 5},
          {1, 1, 4}}

出力: 2 7

解説

クエリ1: 範囲 [4, 8] に含まれる配列要素を数えます。該当するのは 5 と 4 の2つなので、個数は 2 です。

クエリ2: arr[6] を 5 に更新します。更新後の配列は arr[] = {1, 5, 2, 4, 2, 2, 5, 1, 3} となります。

クエリ3: 範囲 [1, 4] に含まれる配列要素を数えます。該当するのは 1, 2, 4, 2, 2, 1, 3 の7つなので、個数は 7 です。

解法アプローチ1: 線形探索(単純な方法)

最もシンプルな解決策は、カウントのクエリが来るたびに配列を直接走査し、L ≤ 要素 ≤ R を満たす要素をすべて数える方法です。

実装例

#include <iostream>
using namespace std;
int countElementInRange(int arr[], int N, int L, int R){
    int ValueCount = 0;
    for (int i = 0; i < N; i++) {
       if (arr[i] >= L && arr[i] <= R) {
          ValueCount++;
       }
    }
    return ValueCount;
}
int main() {
    int arr[] = {1, 5, 2, 4, 2, 2, 3, 1, 3};
    int N = sizeof(arr) / sizeof(arr[0]);
    int Q = 3;
    int query[Q][3] = { {1, 4, 8},{2, 6, 5},{1, 1, 4}};
    for(int i = 0; i < Q; i++){
       if(query[i][0] == 1)
          cout<<"The count of array elements with value in given range is " <<countElementInRange(arr,N, query[i][1], query[i][2])<<endl;
       else if(query[i][0] == 2){
          cout<<"Updating Value \n";
          arr[query[i][1]] = query[i][2];
       }
    }
    return 0;
}

出力

The count of array elements with value in given range is 2
Updating Value
The count of array elements with value in given range is 7

計算量の分析

このアプローチでは、範囲カウントのクエリごとに配列全体を一度走査する必要があります。そのため、時間計算量は O(Q×N) となります。配列サイズ N やクエリ数 Q が大きくなると処理が遅くなるため、より効率的な方法が求められます。

解法アプローチ2: Binary Indexed Tree(Fenwick Tree)を使う方法

より効率的な解決策として、Binary Indexed Tree(BIT、別名 Fenwick Tree)というデータ構造を利用する方法があります。配列の「値」を木のインデックスとして扱い、各値の出現回数を木に格納することで、組み込みの getSum(累積和取得)操作を使って範囲内の要素数を高速に求められます。

範囲 [L, R] 内の要素数は、次の式で計算できます。

ElementCount[L, R] = getSum(R) - getSum(L - 1)

要素の更新時には、古い値の出現回数を -1、新しい値の出現回数を +1 することで木を正しい状態に保ちます。

実装例

#include <iostream>
using namespace std;
class BinaryIndTree {
    public:
        int* BIT;
        int N;
        BinaryIndTree(int N) {
            this->N = N;
            BIT = new int[N];
            for (int i = 0; i < N; i++) {
                BIT[i] = 0;
            }
        }
        void update(int index, int increment) {
            while (index < N) {
                BIT[index] += increment;
                index += (index & -index);
            }
        }
        int calcSum(int index) {
            int sum = 0;
            while (index > 0) {
                sum += BIT[index];
                index -= (index & -index);
            }
            return sum;
        }
};
void UpdateValue(int* arr, int n, int index, int val, BinaryIndTree* fenwickTree){
    int removedElement = arr[index];
    fenwickTree->update(removedElement, -1);
    arr[index] = val;
    fenwickTree->update(val, 1);
}
int countElementInRange(int* arr, int n, int L, int R, BinaryIndTree* fenwickTree) {
    return fenwickTree->calcSum(R) - fenwickTree->calcSum(L - 1);
}
int main() {
    int arr[] = { 1, 5, 2, 4, 2, 2, 3, 1, 3 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int Q = 3;
    int query[Q][3] = { {1, 4, 8},{2, 6, 5},{1, 1, 4}};
    int N = 100001;
    BinaryIndTree* fenwickTree = new BinaryIndTree(N);
    for (int i = 0; i < n; i++)
        fenwickTree->update(arr[i], 1);
    for(int i = 0; i < Q; i++){
        if(query[i][0] == 1)
            cout<<"The count of array elements with value in given range is "<<countElementInRange(arr, n, query[i][1], query[i][2], fenwickTree)<<endl;
        else if(query[i][0] == 2){
            cout<<"Updating Value \n";
            UpdateValue(arr, n, query[i][1], query[i][2], fenwickTree);
        }
    }
    return 0;
}

出力

The count of array elements with value in given range is 2
Updating Value
The count of array elements with value in given range is 7

まとめ

Fenwick Tree を使ったアプローチでは、要素の更新も範囲の集計もそれぞれ O(log N) で処理できます。初期構築を含めた全体の時間計算量は O((N + Q) log N) となり、線形探索の O(Q×N) と比較して大幅な高速化が期待できます。なお、配列の値の取り得る範囲が非常に大きい場合は、座標圧縮(値を順位に変換する前処理)を組み合わせることで、BIT のメモリ使用量を抑えられる点も覚えておくとよいでしょう。