C++ 数组中的最小-最大范围查询
给定一个包含N个元素的数组Arr[]。目标是从查询索引中找到最小值和最大值。
根据查询，我们得到起始索引和结束索引。
例如
In −Arr[]={1,2,3,4,5}QStart=1QEnd=4
出 -
最小值：2
最大值：5
说明 -在上述查询中，起始索引为1，结束索引为4。在这两个索引之间，Arr中的最小值为2，最大值为5
In −Arr[]={10,12,3,2,5,18}QStart=2QEnd=5
出 -
最小值：2
最大值：18
说明 -在上述查询中，起始索引为2，结束索引为5。在这两个索引之间，Arr中的最小值为2，最大值为18
以下程序中使用的方法如下-
在这种方法中，我们将使用范围lpos到rpos的段树来查找给定查询范围内的最小值和最大值。
获取输入数组Arr[]并查询索引QStart和QEnd。
取类型值的结果。
结构值用于存储使用给定查询在数组中找到的最小值和最大值。
结构值用于存储使用给定查询在数组中找到的最小值和最大值。
函数minMax(structvalue*root1,intnum,intqStart1,intqEnd1)获取查询索引并在索引范围qStart1和qEnd1之间的数组中找到最小值和最大值。
检查是否（qStart1<0ORqEnd1>num-1ORqStart1>qEnd1）。如果为true，则查询中的输入范围无效。
否则，调用minmaxFind(root1,0,num-1,qStart1,qEnd1,0)。
函数minmaxFind(structvalue*root,intstartT,intendT,intqStart,intqEnd,intpos)是一个递归函数。它需要一个指向段树根的指针，当前值的开始和结束索引作为startT和endT。
它还需要查询范围内的开始和结束索引。段树中value的当前索引具有索引pos。
如果(qStart<=startT)ANDif(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(intarr2[],intstartT2,intendT2,structvalue*root2,intpos2)用于为数组arr2[]构造一个段树，索引范围为startT2和endT2，当前值位置为pos2。
函数*createTree(intarr0[],intnum0)用于从给定的数组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<<"请输入有效输入！！";
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<<"最小值： "<<answer.minVal<<endl;
cout<<"最大值： "<<answer.maxVal;
return 0;
}输出结果如果我们运行上面的代码，它将生成以下输出
最小值： 2 最大值： 5