C++の更新で範囲内の最大の製品ペアを見つけるためのクエリ

この問題では、配列arr[]とQクエリが与えられます。各クエリは2つのタイプのいずれかになります。1つ目は、指定された範囲[開始-終了]で最大のペア積を検索します。 2番目にi番目のインデックス要素を値で更新します。私たちのタスクは、クエリを解決して、C++の更新で範囲内の最大の製品ペアを見つけるプログラムを作成することです。

問題を理解するために例を見てみましょう

入力： arr ={4、2、6、9、1}

Q =3

Q1 =[1、1、4]

Q2 =[2、2、3]

Q3 =[1、0、2]

出力： 54、12

説明

クエリ1の場合、1：range ={2、6、9、1}と入力します。最大積6*9 =54

クエリ2の場合、タイプ2：i =2、更新された配列arr [] ={4、2、3、9、1}

クエリ3の場合、1：range ={4、2、3}と入力します。最大積4*3 =12

ソリューションアプローチ

この問題を解決するために、簡単なアプローチがあります。これは、タイプ1のすべてのクエリに対して、配列全体をトラバースし、すべてのペアの積をチェックしてから、それらの中から最大の積ペアを見つけます。

例

#include <iostream>
using namespace std;
int max(int a, int b){
   if(a>b)
      return a;
      return b;
}
int findMaxProductPair(int arr[], int n, int start, int end){
   int maxProd = 0;
   for(int i = start; i <= end; i++){
      for(int j = i+1; j <= end; j++){
         maxProd = max(maxProd, (arr[i]*arr[j]));
      }
   }
   return maxProd;
}
int main(){
   int arr[] = {4, 2, 6, 9, 1, 5};
   int n = 6;
   int Q = 3;
   int query[Q][3] = {{1, 1, 4}, {2, 2, 3}, {1, 0, 2}};
   for(int i = 0; i < Q; i++){
      if(query[i][0] == 1){
         cout<<"The maximum product pair in the range is "<<findMaxProductPair(arr, n, query[i][1], query[i][2])<<"\n";
      }
      else if(query[i][0] == 2){
         cout<<"Updating values...\n";
         arr[query[i][1]] = query[i][2];
      }
   }
   return 0;
}

出力

The maximum product pair in the range is 54
Updating values...
The maximum product pair in the range is 12

このアプローチは優れていますが、最大の積を見つけるには、時間の複雑さを増すアレイ全体をトラバースする必要があります。

効率的なソリューション セグメントツリーデータ構造を使用して、サブ配列の2つの最大要素を格納している可能性があります。そして、製品を返品します。

例

#include <iostream>
using namespace std;
struct segment {
   int maxEle;
   int secMax;
};
segment findMaxProductPair(segment* prodTree, int index, int start, int end, int L, int R) {
   segment result;
   result.maxEle = -1;
   result.secMax = -1;
   if (L > end || R < start || start > end)
      return result;
   if (start >= L && end <= R)
      return prodTree[index];
   int middleIndex = (start + end) / 2;
   segment left = findMaxProductPair(prodTree, 2 * index, start,middleIndex, L, R);
   segment right = findMaxProductPair(prodTree, 2 * index + 1,middleIndex + 1, end, L, R);
   result.maxEle = max(left.maxEle, right.maxEle);
   result.secMax = min(max(left.maxEle, right.secMax),max(right.maxEle, left.secMax));
   return result;
}
void update(segment* prodTree, int index, int start, int end, int i, intupdateVal) {
   if (i < start || i > end)
      return;
   if (start == end) {
      prodTree[index].maxEle = updateVal;
      prodTree[index].secMax = -1;
      return;
   }
   int middleIndex = (start + end) / 2;
   update(prodTree, 2 * index, start, middleIndex, i, updateVal);
   update(prodTree, 2 * index + 1, middleIndex + 1, end, i, updateVal);
   prodTree[index].maxEle = max(prodTree[2 * index].maxEle,prodTree[2 * index + 1].maxEle);
   prodTree[index].secMax = min(max(prodTree[2 * index].maxEle,prodTree[2 * index + 1].secMax), max(prodTree[2 * index + 1].maxEle,prodTree[2 * index].secMax));
}
void buildtree(segment* prodTree, int* arr, int index, int start, int end) {
   if (start > end) {
      return;
   }
   if (start == end) {
      prodTree[index].maxEle = arr[start];
      prodTree[index].secMax = -1;
      return;
   }
   int middleIndex = (start + end) / 2;
   buildtree(prodTree, arr, 2 * index, start, middleIndex);
   buildtree(prodTree, arr, 2 * index + 1, middleIndex + 1, end);
   int maximum = max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].maxEle);
   int secMaximum = min(max(prodTree[2 * index].maxEle, prodTree[2 * index + 1].secMax),max(prodTree[2 * index + 1].maxEle, prodTree[2 * index].secMax));
   prodTree[index].maxEle = maximum;
   prodTree[index].secMax = secMaximum;
}
int main() {
   int arr[] = {4, 2, 6, 9, 1, 5};
   int n = 6;
   int Q = 3;
   segment* prodTree = new segment[4 * n + 1];
   buildtree(prodTree, arr, 1, 0, n - 1);
   int query[Q][3] = {{1, 1, 4}, {2, 2, 3}, {1, 0, 2}};
   for(int i = 0; i < Q; i++){
      if(query[i][0] == 1){
         segment result = findMaxProductPair(prodTree, 1, 0, n - 1,query[i][1] , query[i][2]);
         cout<<"The maximum product pair in the range is "<<(result.maxEle*result.secMax)<<"\n";
      }
      else if(query[i][0] == 2){
         cout<<"Updating values...\n";
      update(prodTree, 1, 0, n - 1, query[i][1], query[i][2]);
      }
   }
   return 0;
}

出力

The maximum product pair in the range is 54
Updating values...
The maximum product pair in the range is 12