【C++】数値の追加・削除・最大値と最小値の差を返すクエリ処理の実装方法

この記事では、Q個のクエリを処理する問題を取り上げます。クエリには次の3種類があります。

• クエリ1：リストに数値Nを追加する

• クエリ2：リストから数値Nを削除する

• クエリ3：リスト内の最大値と最小値の差を返す

私たちのタスクは、これらのクエリ（追加・削除・最大値と最小値の差の取得）を処理するプログラムをC++で作成することです。

問題の概要

リストに対して実行するQ個のクエリが与えられます。クエリには「要素の追加」「要素の削除」「リストの最大値と最小値の差を求める」の3種類があります。まず与えられたクエリを順番に処理してリストを構築し、クエリ3が呼ばれた時点でリスト内の最大値と最小値の差を計算して返します。

具体例を使って問題を確認してみましょう。

入力： Q = 6

Query (1, 4)

Query (1, 9)

Query (1, 6)

Query (2, 4)

Query (1, 3)

Query (3)

出力： 6

出力の解説

すべてのクエリを処理し終えた時点で、リストは {9, 6, 3} となっています。

• 最大値 → 9

• 最小値 → 3

• 差 → 9 − 3 = 6

解法アプローチ①：配列を使うシンプルな方法

最も基本的な解法は、各クエリをそのまま素直に処理することです。手順は以下の通りです。

• 配列を初期化する

• クエリタイプ1の場合：配列の末尾に要素を追加する

• クエリタイプ2の場合：配列から該当する要素を探して削除する

• クエリタイプ3の場合：配列全体を走査して最大値と最小値を求め、その差を返す

実装例

#include <iostream>
using namespace std;
void solveQuerry(int type, int item){
   int list[100];
   static int index = 0;
   if(type == 1){
      list[index] = item;
      index++;
   }
   else if(type == 2){
      for(int i = 0; i <= index; i++)
      if(list[i] == item ){
         list[i] = 0;
         break;
         }
      }
      else if(type == 3){
         int max = -100, min = 100;
      for(int i = 0; i< index; i++){
         if(list[i] == 0)
            i++;
         if(list[i] > max)
            max = list[i];
         if(list[i] < min)
            min = list[i];
      }
   cout<<"The difference between the maximum and minimum elements of the list is "<<(max - min);
   }
}
int main() {
   int Q = 6;
   int query[Q][2] = {{1, 5}, {1, 9}, {1, 6}, {2, 4}, {1, 3}, {3, 0}};
   for(int i = 0; i< Q; i++){
      solveQuerry(query[i][0], query[i][1]);
   }
}

実行結果

The difference between the maximum and minimum elements of the list is 6

この方法では、削除や最大・最小の検索に線形時間O(N)がかかるため、クエリ数や要素数が増えると処理が遅くなるという欠点があります。

解法アプローチ②：平衡二分探索木（std::set）を使う効率的な方法

単純な配列の代わりに適切なデータ構造を選ぶことで、検索処理を大幅に効率化できます。ここでは、自己平衡二分探索木として実装されているstd::setを使用します。

std::setは要素を常にソートされた状態で保持するため、次のような特徴があります。

• 最大値はコンテナの末尾に存在し、rbegin()メソッドでアクセスできる

• 最小値はコンテナの先頭に存在し、begin()メソッドでアクセスできる

• 挿入（insert）・削除（erase）・検索はいずれもO(log N)で実行できる

そのため、クエリの数が多い場合でも高速に動作するのが大きな利点です。

実装例

#include <bits/stdc++.h>
using namespace std;
set<int> myList;
void solveQuerry(int type, int num){
   if(type == 1){
      myList.insert(num);
   }
   else if(type == 2){
      myList.erase(num);
   }
   else if(type == 3){
      int max = *(myList.rbegin());
      int min = *(myList.begin());
      cout<<"The difference between the maximum and minimum elements of the list is "<<(max - min);
   }
}
int main() {
   int Q = 6;
   int query[Q][2] = {{1, 5}, {1, 9}, {1, 6}, {2, 4}, {1, 3}, {3, 0}};
   for(int i = 0; i< Q; i++){
      solveQuerry(query[i][0], query[i][1]);
   }
}

実行結果

The difference between the maximum and minimum elements of the list is 6

まとめ

本記事では、要素の追加・削除・最大値と最小値の差の取得という3種類のクエリを処理するC++プログラムを紹介しました。配列を使ったシンプルな実装は理解しやすいものの、各操作にO(N)かかるため非効率です。一方、std::set（自己平衡二分探索木）を利用すれば、すべての操作をO(log N)で行え、最大値と最小値にも即座にアクセスできます。実務や競技プログラミングにおいては、データ構造を適切に選択することの重要性を示す良い例と言えるでしょう。