C++ 数组中的最小-最大范围查询
给定一个包含 N 个元素的数组 Arr[]。目标是根据查询的索引找到最小值和最大值。
根据查询，我们给出了起始索引和结束索引。
例如
在 − Arr[] = { 1, 2, 3, 4, 5 } QStart = 1 QEnd = 4
Out −
最小值:2
最大值:5
说明 −在上述查询中，起始索引为 1，结束索引为 4。在这两个索引之间，Arr 中的最小值为 2，最大值为 5
In − Arr[] = { 10, 12, 3, 2, 5, 18 } QStart = 2 QEnd = 5
Out −
最小值:2
最大值:18
说明 − 在上述查询中，起始索引为 2，结束索引为 5。在这两个索引之间，Arr 中的最小值为 2，最大值为 18
以下程序中使用的方法如下 −
在此方法中，我们将使用线段树，针对 lpos 到 rpos 范围，查找给定查询范围内的最小值和最大值。
获取输入数组 Arr[] 以及查询索引 QStart 和 QEnd。
获取 value 类型的结果。
结构体 value 用于存储在数组中使用给定查询找到的最小值和最大值。
结构体 value 用于存储在数组中使用给定查询找到的最小值和最大值。
函数 minMax(struct value *root1, int num, int qStart1, int qEnd1) 获取查询索引，并在索引范围 qStart1 和 qEnd1 之间的数组中查找最小值和最大值。
检查是否 ( qStart1 < 0 或qEnd1 > num-1 或 qStart1 > qEnd1)。如果为真，则查询中的输入范围无效。
否则，调用 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 中的最大值。
返回 temp。
函数 segmentsTree(int arr2[], int startT2, int endT2, struct value *root2, int pos2) 用于为数组 arr2[] 构建线段树，其索引范围为 startT2 和 endT2，当前值位置为 pos2。
函数 *createTree(int arr0[], int num0) 用于从给定数组 arr0 构建线段树。此函数为线段树分配内存，并调用 segments() 进行内存分配。
示例
#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
