在 c++ 中解决段树以外的范围查询的有效方法是什么?

Question

我正在尝试理解段树。我在hackerrank(链接(上尝试了一个问题，并尝试在c ++ link中使用geeksforgeeks代码。但是，我在第 19 行遇到了转储值问题。

int right = RMQUtil(st, mid+1, se, qs, qe, 2*index+2); // why this is getting a dump value here?

我也发现这将超时。有没有其他有效的方法来解决这个问题？ 我想知道为什么我的代码不能有效地解决这个问题，并且需要在c ++中有一个更好的解决方案

这是我尝试过的代码。

// you will see the comments on the geeksforgeeks code in the link. I used it here.
#include <bits/stdc++.h> 
using namespace std; 
int minVal(int x, int y) { return (x < y); }  
int getMid(int s, int e) { return s + (e -s)/2; } 
int RMQUtil(int *st, int ss, int se, int qs, int qe, int index) 
{ 
if (qs <= ss && qe >= se) 
return st[index]; 
if (se < qs || ss > qe) 
return INT_MAX; 
int mid = getMid(ss, se);
int left = RMQUtil(st, ss, mid, qs, qe, 2*index+1);
int right = RMQUtil(st, mid+1, se, qs, qe, 2*index+2); // why this is getting a dump value here?
return min({left, right, left+right},minVal); 
} 
int RMQ(int *st, int n, int qs, int qe) 
{ 
if (qs < 0 || qe > n-1 || qs > qe) 
{ 
cout<<"Invalid Input"; 
return -1; 
} 
return RMQUtil(st, 0, n-1, qs, qe, 0); 
} 
int constructSTUtil(int arr[], int ss, int se, int *st, int si) 
{ 
if (ss == se) 
{ 
st[si] = arr[ss]; 
return arr[ss]; 
}  
int mid = getMid(ss, se);
int left = constructSTUtil(arr, ss, mid, st, si*2+1); 
int right = constructSTUtil(arr, mid+1, se, st, si*2+2);
st[si] = min({left, right, left+right},minVal); 
return st[si]; 
}  
int *constructST(int arr[], int n) 
{ 
int x = (int)(ceil(log2(n)));  
int max_size = 2*(int)pow(2, x) - 1; 
int *st = new int[max_size];  
constructSTUtil(arr, 0, n-1, st, 0); 
return st; 
}
void updateSTUtil(int* st, int si, int ss, int se, int k, int v){
if (k < ss or k > se)
return;
if (ss == se){
st[si] = v;
return;
}
int mid = getMid(ss, se);
updateSTUtil(st, 2 * si +1, ss, mid, k, v);
updateSTUtil(st, 2 * si +2, mid + 1, se, k, v);
st[si] = min({st[2 * si +1], st[2 * si +2], st[2 * si +1] + st[2 * si +2]}, minVal);
}
void updateST(int n, int* st, int k, int v){
updateSTUtil(st, 0, 0, n-1, k, v);  
}
int main() 
{ 
int t,n,q,a,ss,se;
scanf("%d",&t);
for (int i=0; i<t; i++){
scanf("%d",&n);
int arr[n];
for (int j=0 ; j<n; j++){
cin >> arr[j];
}
int *st = constructST(arr, n);
scanf("%d",&q);
for (int i=0; i<q; i++){
scanf("%d%d%d",&a,&ss,&se);
if (a == 0){
updateST(n, st, ss-1, se);
}
else{
cout << RMQ(st, n, ss-1, se-1)<<endl;
}
}
} 
return 0; 
} 

:)

Answer 1

检查二分索引树或芬威克树。

检查这个

https://www.geeksforgeeks.org/binary-indexed-tree-range-update-range-queries/

和一个 也许根据您想要的间隔树，例如。如果要查找范围内的最大值或最小值。