Min-Max Range Queries ในอาร์เรย์ใน C ++

รับอาร์เรย์ Arr[] ที่มีองค์ประกอบ N เป้าหมายคือการหาค่าต่ำสุดและสูงสุดจากดัชนีของข้อความค้นหา

ตามคำค้นหา เราได้รับดัชนีเริ่มต้นและดัชนีสิ้นสุด

ตัวอย่าง

ใน − Arr[] ={ 1, 2, 3, 4, 5 } QStart =1 QEnd =4

ออก −

มูลค่าขั้นต่ำ :2

มูลค่าสูงสุด :5

คำอธิบาย −ในการสืบค้นข้างต้น ดัชนีเริ่มต้นคือ 1 และดัชนีสิ้นสุดคือ 4 ระหว่างดัชนีทั้งสองนี้ ค่าต่ำสุดใน Arr คือ 2 และค่าสูงสุดคือ 5

ใน − Arr[] ={ 10, 12, 3, 2, 5, 18 } QStart =2 QEnd =5

ออก −

มูลค่าขั้นต่ำ :2

มูลค่าสูงสุด :18

คำอธิบาย − ในแบบสอบถามข้างต้น ดัชนีเริ่มต้นคือ 2 และดัชนีสิ้นสุดคือ 5 ระหว่างดัชนีทั้งสองนี้ ค่าต่ำสุดใน Arr คือ 2 และค่าสูงสุดคือ 18

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −

ในแนวทางนี้ เราจะใช้แผนผังกลุ่มสำหรับช่วง lpos ถึง rpos เพื่อค้นหาค่าต่ำสุดและสูงสุดในช่วงการสืบค้นที่กำหนด

• ใช้อาร์เรย์อินพุต Arr[] และดัชนีแบบสอบถาม QStart และ QEnd

• นำผลลัพธ์ของค่าประเภท

• ค่าโครงสร้างใช้เพื่อเก็บค่าต่ำสุดและสูงสุดที่พบในอาร์เรย์โดยใช้การสืบค้นที่กำหนด

• ค่าโครงสร้างใช้เพื่อเก็บค่าต่ำสุดและสูงสุดที่พบในอาร์เรย์โดยใช้การสืบค้นที่กำหนด

• ฟังก์ชัน minMax(ค่าโครงสร้าง *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(ค่าโครงสร้าง *root, int startT, int endT, int qStart, int qEnd, int pos) เป็นฟังก์ชันแบบเรียกซ้ำ ต้องใช้ตัวชี้เพื่อแบ่งกลุ่ม tree-root ดัชนีเริ่มต้นและสิ้นสุดของค่าปัจจุบันเป็น startT และ endT

• นอกจากนี้ยังใช้ดัชนีเริ่มต้นและสิ้นสุดในช่วงการสืบค้น ดัชนีค่าปัจจุบันในแผนผังกลุ่มมีตำแหน่งดัชนี

• ถ้า (qStart <=startT) และ 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, ค่าโครงสร้าง *root2, int pos2) ใช้เพื่อสร้างแผนผังกลุ่มสำหรับอาร์เรย์ arr2[] โดยมีช่วงดัชนีเป็น startT2 และ endT2 และตำแหน่งค่าปัจจุบันคือ pos2

• ฟังก์ชัน *createTree(int arr0[], int num0) ใช้เพื่อสร้างแผนผังส่วนจากอาร์เรย์ที่กำหนด arr0 ฟังก์ชันนี้จะจัดสรรหน่วยความจำสำหรับแผนผังเซ็กเมนต์และเรียกใช้เซกเมนต์ทรี () สำหรับการจัดสรรหน่วยความจำ

ตัวอย่าง

#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