Я пытаюсь понять деревья сегментов. Я попытался решить проблему с хакерранком ( ссылка ) и попытался использовать код geeksforgeeks в c ++ ссылка . Тем не менее, у меня возникла проблема со значением дампа в строке 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;
}
:)