M個の範囲トグル操作後のバイナリ配列を求めるアルゴリズム

今回は、M個の範囲トグル（反転）コマンドを適用した後のバイナリ配列の最終状態を求める問題を解説します。
まず、n個の要素からなるバイナリ配列を用意します。各要素は0または1の値を持ち、初期状態ではすべての要素が0です。続いて、M個のコマンドが与えられます。各コマンドは開始インデックスaと終了インデックスbを含みます。つまり、command(a, b)は、位置aの要素から位置bの要素までの範囲に対して適用されることを意味します。コマンドが実行されると、その範囲内のすべての値がトグルされます（0は1に、1は0に切り替わります）。

アルゴリズム

toggleCommand(arr, a, b)

Begin
    for each element e from index a to b, do
        toggle the e and place into arr at its position.
    done
End

アルゴリズムの考え方は非常にシンプルで、指定された範囲a〜bの各要素を順番に走査し、ビットごとの排他的論理和（XOR）を使って値を反転させるだけです。

C++による実装例

#include <iostream>
using namespace std;
void toggleCommand(int arr[], int a, int b){
    for(int i = a; i <= b; i++){
        arr[i] ^= 1; // 範囲a〜bの各ビットを反転
    }
}
void display(int arr[], int n){
    for(int i = 0; i<n; i++){
        cout << arr[i] << " ";
    }
    cout << endl;
}
int main() {
    int arr[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
    int n = sizeof(arr)/sizeof(arr[0]);
    display(arr, n);
    toggleCommand(arr, 3, 6);
    toggleCommand(arr, 8, 10);
    toggleCommand(arr, 2, 7);
    display(arr, n);
}

出力結果

0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 1 1 1 0

処理の流れの解説

上記の例では、12個の要素を持つ配列に対して3つのコマンドを順に実行しています。

• toggleCommand(arr, 3, 6)：インデックス3〜6の要素が0から1に変わります。
• toggleCommand(arr, 8, 10)：インデックス8〜10の要素が0から1に変わります。
• toggleCommand(arr, 2, 7)：インデックス2〜7の要素を反転します。すでに1になっている3〜6は0に戻り、0だった2と7は1になります。

その結果、最終的な配列は「0 0 1 0 0 0 0 1 1 1 1 0」となります。

計算量と効率化のポイント

このシンプルな実装では、1回のコマンドにつき最大O(n)の処理が必要となるため、全体の計算量はO(M×n)になります。nやMが非常に大きい場合（例えば10^5以上の入力）、各コマンドを直接反映する代わりに、差分配列やXOR累積和のテクニックを用いることで、各コマンドをO(1)で記録し、最後に一度だけ累積を計算するO(n + M)の効率的なアプローチに改善できます。競技プログラミングなど大規模データを扱う場面では、この最適化が重要になります。