【C++】指定範囲内に特定の数字が存在するかどうかを判定するクエリ処理

この記事では、配列 arr[] と複数のクエリ（各クエリは L、R、val の3つの値で構成される）が与えられたとき、C++ を使って「指定された範囲内に特定の数字が存在するか」を判定するプログラムを作成する方法を解説します。

問題の概要

各クエリに対して、範囲 L ～ R の間に要素 val が含まれているかどうかを確認する必要があります。

具体例で確認してみましょう。

入力：arr[] = {4, 8, 1, 7, 2, 9, 3, 5, 1}

Q = 3

query = {{1, 4, 3}, {0, 2, 1}, {4, 7, 2}}

出力：

Not Present
Present
Present

出力の解説

クエリ1： 範囲 [1, 4] に対応する部分配列は {8, 1, 7, 2}。この中に 3 は存在しないため「Not Present」。

クエリ2： 範囲 [0, 2] に対応する部分配列は {4, 8, 1}。この中に 1 は存在するため「Present」。

クエリ3： 範囲 [4, 7] に対応する部分配列は {2, 9, 3, 5}。この中に 2 は存在するため「Present」。

解法アプローチ①：単純な走査による方法

最もシンプルな解法は、部分配列を順番に走査し、指定された範囲内に目的の要素が存在するかを1つずつチェックする方法です。

サンプルコード

#include <iostream>
using namespace std;
bool isElementPresent(int arr[], int L, int R, int val){
   for(int i = L; i <= R; i++ ){
      if(arr[i] == val){
         return true;
      }
   }
   return false;
}
int main(){
   int arr[] = {4, 8, 1, 7, 2, 9, 3, 5, 1};
   int Q = 3;
   int query[Q][3] = {{1, 4, 3}, {0, 2, 1}, {4, 7, 2 }};
   for(int i = 0; i < Q; i++){
      cout<<"For Query "<<(i+1);
      if(isElementPresent(arr, query[i][0], query[i][1], query[i][2]))
         cout<<": The given digit "<<query[i][2]<<" is present in the given range\n";
      else
         cout<<": The given digit "<<query[i][2]<<" is not present in the given range\n";
   }
   return 0;
}

実行結果

For Query 1: The given digit 3 is not present in the given range
For Query 2: The given digit 1 is present in the given range
For Query 3: The given digit 2 is present in the given range

この方法はループを使用するため、時間計算量は O(Q × N) となります。ここで Q はクエリの数、N は配列の長さです。データ量やクエリ数が増えると処理が遅くなるため、より効率的な手法が求められます。

解法アプローチ②：セグメント木を使った効率的な方法

より良い解法として、考えられるすべての数字（0～9）を格納できるセグメント木を活用する方法があります。ノード内の重複要素を避けるために set データ構造（重複要素を自動的に排除する特性を持つ）を使用します。これにより、各ノードに含まれる要素数を最大10個に抑えることができます。

その後、各クエリに対して、指定された範囲内に該当する要素が存在するかどうかをセグメント木を使って高速に判定できます。この手法では各クエリの計算量を大幅に削減でき、大量のクエリを扱う場合に特に有効です。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
set<int> SegTree[36];
void buildSegmentTree(int* arr, int index, int start, int end) {
   if (start == end) {
      SegTree[index].insert(arr[start]);
      return;
   }
   int middleEle = (start + end) >> 1;
   buildSegmentTree(arr, 2 * index, start, middleEle);
   buildSegmentTree(arr, 2 * index + 1, middleEle + 1, end);
   for (auto it : SegTree[2 * index])
      SegTree[index].insert(it);
   for (auto it : SegTree[2 * index + 1])
      SegTree[index].insert(it);
}
bool isElementPresent(int index, int start, int end, int L, int R, int val){
   if (L <= start && end <= R) {
      if (SegTree[index].count(val) != 0) {
         return true;
      }
      else
         return false;
    }
   if (R < start || end < L) {
      return false;
   }
   int middleEle = (start + end) >> 1;
   bool isPresentInLeftSubArray = isElementPresent((2 * index), start,middleEle, L, R, val);
   bool isPresentInRightSubArray = isElementPresent((2 * index + 1),(middleEle + 1), end, L, R, val);
   return isPresentInLeftSubArray or isPresentInRightSubArray;
}
int main(){
   int arr[] = {4, 8, 1, 7, 2, 9, 3, 5, 1};
   int n = sizeof(arr)/sizeof(arr[0]);
   int Q = 3;
   int query[Q][3] = {{1, 4, 3}, {0, 2, 1}, {4, 7, 2 }};
   buildSegmentTree(arr, 1, 0, (n - 1));
   for(int i = 0; i < Q; i++){
      cout<<"For Query "<<(i+1);
      if(isElementPresent(1, 0, (n - 1), query[i][0], query[i][1], query[i][2]))
         cout<<": The given digit "<<query[i][2]<<" is present in the given range\n";
      else
         cout<<": The given digit "<<query[i][2]<<" is not present in the given range\n";
   }
   return 0;
}

実行結果

For Query 1: The given digit 3 is not present in the given range
For Query 2: The given digit 1 is present in the given range
For Query 3: The given digit 2 is present in the given range

まとめ

単純な線形探索による方法は実装が簡単ですが、計算量が O(Q × N) となるため大規模なデータには不向きです。一方、セグメント木と set を組み合わせた方法では、前処理に O(N log N) の計算量が必要ですが、各クエリを高速に処理できるため、クエリ数が多い場合に優れたパフォーマンスを発揮します。用途に応じて最適な手法を選択しましょう。