C++で範囲モジュール（Range Module）を実装する方法

数値の範囲（レンジ）を追跡する「範囲モジュール」を設計してみましょう。このモジュールは半開区間 [left, right) の形で数値の区間を管理し、以下の3つの操作を効率的に実行できることが求められます。

実装すべきインターフェース

• addRange(left, right)：半開区間 [left, right) に含まれるすべての実数を追跡対象に追加します。既存の追跡区間と部分的に重なる場合でも、まだ追跡されていない部分だけが新たに追加されます。
• queryRange(left, right)：区間 [left, right) 内のすべての実数が現在追跡中であれば true を返します。
• removeRange(left, right)：区間 [left, right) 内で現在追跡しているすべての実数の追跡を停止します。

アルゴリズムの考え方

この問題は、std::map を使って「区間の開始位置をキー、終了位置を値」として管理するのが有効です。各区間が隣接・重なったタイミングでマージ（統合）することで、常に整理された状態を保てます。手順は以下の通りです。

addRange(left, right)

• まず removeRange(left, right) を呼び出して重複部分を取り除きます。
• m[left] := right を設定します。
• left の位置を指すイテレータ it を取得します。
• it が先頭要素ではなく、直前の要素の終了値が left と一致する場合は、it を1つ前へ移動し、その終了値を right に更新したうえで、m から left を削除します（前の区間とのマージ）。
• it が末尾の前の要素であり、次の要素の開始値が right と一致する場合は、it の終了値を次の要素の終了値に更新し、次の要素を削除します（後ろの区間とのマージ）。

queryRange(left, right)

• upper_bound(left) で、left より大きいキーのうち最初の位置 it を取得します。
• マップが空、または it が先頭要素の場合は false を返します。
• it を1つ前へ移動し、その終了値が right 以上であれば true を返します。

removeRange(left, right)

• マップが空であれば何もしません。
• lower_bound(left) で位置 it を取得し、先頭要素でなければ1つ前へ移動します。
• 削除予定のキーを格納する配列 v を用意します。
• while ループで、it が末尾ではなく開始値が right 未満である限り以下を繰り返します。
  • 開始値が left 未満かつ終了値が left より大きい場合：一時変数 temp に終了値を保存し、終了値を left に縮めます。temp が right より大きければ、m[right] := temp として残りの区間を登録します。
  • 開始値が left 以上の場合：そのキーを v に追加し、終了値が right より大きければ m[right] := 終了値 として残りを登録します。
  • it を1つ進めます。
• 最後に、v に記録したすべてのキーをマップから削除します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
class RangeModule {
public:
   map <int, int> m;
   RangeModule() {
   }
   void addRange(int left, int right) {
      removeRange(left, right);
      m[left] = right;
      map <int, int> :: iterator it = m.find(left);
      if(it != m.begin() && prev(it)->second == left){
         it--;
         it->second = right;
         m.erase(left);
      }
      if(it != prev(m.end()) && next(it)->first == right){
         it->second = next(it)->second;
         m.erase(next(it));
      }
   }
   bool queryRange(int left, int right) {
      map <int, int> :: iterator it = m.upper_bound(left);
      if(m.empty() || it == m.begin())return false;
      it--;
      return it->second >= right;
   }
   void removeRange(int left, int right) {
      if(m.empty())return;
      map <int, int> :: iterator it = m.lower_bound(left);
      if(it != m.begin())it--;
      vector <int> v;
      while(it != m.end() && it->first < right){
         if(it->first < left && it->second > left){
            int temp = it->second;
            it->second = left;
            if(temp > right){
               m[right] = temp;
            }
         }else if(it->first >= left){
            v.push_back(it->first);
            if(it->second > right){
               m[right] = it->second;
            }
         }
         it++;
      }
      for(int i = 0; i < v.size(); i++){
         m.erase(v[i]);
      }
   }
};
main(){
   RangeModule ob;
   ob.addRange(10,20);
   ob.removeRange(14,16);
   cout << (ob.queryRange(10,14)) << endl;
   cout << (ob.queryRange(13,15)) << endl;
   cout << (ob.queryRange(16,17));
}

入力

Add range (10,20)
Remove Range (14,16)
Check ranges (10,14), (13,15), (16,17)

出力

1
0
1

このように、区間を std::map で管理し、挿入・削除のたびに隣接区間を適切にマージ・分割することで、3つの操作すべてを効率的に実現できます。各操作の計算量は O(log n + k)（k は処理に関わる区間数）となり、大量の区間操作にも対応可能です。