C++の配列の最小-最大範囲クエリ

N個の要素を含む配列Arr[]が与えられます。目標は、クエリのインデックスから最小値と最大値を見つけることです。

クエリによると、開始インデックスと終了インデックスが与えられます。

例

で − arr [] ={1、2、3、4、5} QStart =1 QEnd =4

アウト −

最小値：2

最大値：5

説明 −上記のクエリでは、開始インデックスは1、終了インデックスは4です。これら2つのインデックスの間で、Arrの最小値は2、最大値は5です。

で − arr [] ={10、12、3、2、5、18} QStart =2 QEnd =5

アウト −

最小値：2

最大値：18

説明 −上記のクエリでは、開始インデックスは2、終了インデックスは5です。これら2つのインデックスの間で、Arrの最小値は2、最大値は18です。

以下のプログラムで使用されるアプローチは次のとおりです-

このアプローチでは、lposからrposの範囲のセグメントツリーを使用して、指定されたクエリ範囲の最小値と最大値を見つけます。

• 入力配列Arr[]を取得し、インデックスQStartとQEndをクエリします。

• タイプ値の結果を取得します。

• 構造体の値は、特定のクエリを使用して配列で見つかった最小値と最大値を格納するために使用されます。

• 構造体の値は、特定のクエリを使用して配列で見つかった最小値と最大値を格納するために使用されます。

• 関数minMax（struct value * root1、int num、int qStart1、int qEnd1）は、クエリインデックスを取得し、インデックス範囲qStart1とqEnd1の間の配列で最小値と最大値を見つけます。

• （qStart1 <0 OR qEnd1> num-1 OR qStart1> qEnd1）かどうかを確認します。 trueの場合、クエリの入力範囲は無効です。

• それ以外の場合は、minmaxFind（root1、0、num-1、qStart1、qEnd1、0）を呼び出します。

• 関数minmaxFind（struct value * root、int startT、int endT、int qStart、int qEnd、int pos）は再帰関数です。これは、ツリールートをセグメント化するためのポインタを取り、現在の値の開始インデックスと終了インデックスをstartTおよびendTとして取得します。

• また、クエリ範囲の開始インデックスと終了インデックスを取ります。セグメントツリーの現在の値のインデックスには、インデックスposがあります。

• （qStart <=startT）AND if（qEnd> =endT）の場合、現在の値のセグメントは指定された範囲の一部です。したがって、その値で最小値と最大値を返します。

• 範囲外の場合は、現在の値をminValとmaxValで更新します。

• 現在の部分が指定された範囲と重複する場合：-

• middl =startT +（endT --startT）/2を取ります。

• p1とp2を2*pos+1と=2* pos+2とします。

• lposをlpos=minmaxFind（root、startT、middl、qStart、qEnd、p1）として更新し、rposをminmaxFind（root、middl + 1、endT、qStart、qEnd、p2）として更新します。

• temp.minValをlpos.minValとrpos.minValの最小値として設定します。

• temp.maxValをlpos.maxValとrpos.maxValの最大値として設定します。

• 戻り温度。

• 関数segmentTree（int arr2 []、int startT2、int endT2、struct value * root2、int pos2）は、インデックス範囲がstartT2およびendT2で、現在の値の位置がpos2である配列arr2[]のセグメントツリーを構築するために使用されます。

• 関数*createTree（int arr0 []、int num0）は、指定された配列arr0からセグメントツリーを構築するために使用されます。この関数は、セグメントツリーにメモリを割り当て、メモリ割り当てのためにsegmentTree（）を呼び出します。

例

#include<bits/stdc++.h>
using namespace std;
struct value{
   int minVal;
   int maxVal;
};
struct value minmaxFind(struct value *root, int startT, int endT, int qStart,
   int qEnd, int pos){
   struct value temp, lpos ,rpos;
   if (qStart <= startT) {
      if( qEnd >= endT)
         { return root[pos]; }
   }
   if (endT < qStart || startT > qEnd) {
      temp.minVal = 9999;
      temp.maxVal = -9999;
      return temp;
   }
   int middl = startT + ( endT - startT )/2;
   int p1=2*pos+1;
   int p2=2*pos+2;
   lpos = minmaxFind(root, startT, middl, qStart, qEnd, p1);
   rpos = minmaxFind(root, middl+1, endT, qStart, qEnd, p2);
   temp.minVal = (lpos.minVal<rpos.minVal) ? lpos.minVal : rpos.minVal ;
   temp.maxVal = (lpos.maxVal>rpos.maxVal) ? lpos.maxVal : rpos.maxVal ;
   return temp;
}
struct value minMax(struct value *root1, int num, int qStart1, int qEnd1){
   struct value temp1;
   if (qStart1 < 0 || qEnd1 > num-1 || qStart1 > qEnd1){
      cout<<"Please enter Valid input!!";
      temp1.minVal = 9999;
      temp1.maxVal = -9999;
      return temp1;
   }
   return minmaxFind(root1, 0, num-1, qStart1, qEnd1, 0);
}
void segmentTree(int arr2[], int startT2, int endT2, struct value *root2, int pos2){ 
   if (startT2 == endT2) { 
      root2[pos2].minVal = arr2[startT2];
      root2[pos2].maxVal = arr2[startT2];
      return ;
   }
   int p1=pos2*2+1;   
   int p2=pos2*2+2;
   int middl2 = startT2+(endT2-startT2)/2;
   segmentTree(arr2, startT2, middl2, root2, p1);
   segmentTree(arr2, middl2+1, endT2, root2, p2);
   root2[pos2].minVal = root2[p1].minVal<root2[p2].minVal ? root2[p1].minVal : root2[p2].minVal;
   root2[pos2].maxVal = root2[p1].maxVal>root2[p2].maxVal ? root2[p1].maxVal : root2[p2].maxVal;
}
struct value *createTree(int arr0[], int num0) { 
   int height = (int)(ceil(log2(num0)));
   int maxS = 2*(int)pow(2, height) - 1;
   struct value *root0 = new struct value[maxS];
   segmentTree(arr0, 0, num0-1, root0, 0);
   return root0;
}
int main() { 
   int Arr[] = { 1, 2, 3, 4, 5 };
   int length = sizeof(Arr)/sizeof(Arr[0]);
   struct value *tree = createTree(Arr, length);
   int QStart = 1;
   int QEnd = 4;
   struct value answer=minMax(tree, length, QStart, QEnd);
   cout<<"Minimum Value : "<<answer.minVal<<endl;
   cout<<"Maximum Value : "<<answer.maxVal;
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます

Minimum Value : 2
Maximum Value : 5