0

Estoy tratando de implementar un segment tree con contenedores de la STL para resolver un problema que involucra retornar el valor mínimo de un subsegmento de un arreglo de n elementos. Me dan un arreglo de N elementos y Q peticiones en las que recibo dos enteros que representan el intervalo del arreglo en el que buscaré el elemento minimo de ese intervalo. Si sé que ese error es porqué ocurrió un stack overflow, por alguna funcion recursiva que nunca para o porque trato de acceder a una posición sin memoria del arreglo, pero no logro deducir en donde está el problema. aquí adjunto el código

#include <iostream>
#include <vector>

using namespace std;

class segmentTree{
     vector<int> t;
     vector<int> A;
     public:
         segmentTree(vector <int> &v){
                 A = v;
                 t.resize(4*A.size());
         }
         void st_build(int vertex, int L, int R);
         int st_rmq(int vertex, int L, int R, int i, int j);
         int st_rmq(int i, int j);
};

void segmentTree::st_build(int vertex, int L, int R){
    if(L == R)                          //como  L = R, cualquiera de los dos esta bien
      t[vertex] = L;                        // almacenamos el índice.
    else{
      int nL = 2 * vertex, nR = 2 * vertex + 1;
      st_build(nL, L, (L + R)/2);
      st_build(nR, (L + R)/2 + 1, R);
      int lContent = t[nL], rContent = t[nR];
      int lValue = A[lContent], rValue = A[rContent];
      t[vertex] = (lValue <= rValue) ? lContent : rContent;
    }
 }

int segmentTree::st_rmq(int vertex, int L, int R, int i, int j){
    if(i > R || j < L) return -1;               //el segmento está fuera del rango de busqueda
    if(L >= i && R >= j) return  t[vertex];     // el segmento está dentro del rango.
        
    //calcula la posición mínima en ambas partes del intervalo
    int p1 = st_rmq(2 * vertex, L, (L + R)/2, i, j);
    int p2 = st_rmq(2 * vertex + 1, (L + R)/2 + 1, R, i, j);
        
    //regresa la posición en donde está el elemento mínimo 
    if(p1 == -1) return p2;                 
    if(p2 == -1) return p1;
    return (A[p1] <= A[p2]) ? p1 : p2;
} 

int segmentTree::st_rmq(int i, int j){
   return st_rmq(1, 0, (int)A.size() - 1, i, j);
}

int main(){
   int N, Q, tmp, i, j, inx, ans; vector <int> v;
   cin >> N;
   for (int i = 0; i < N; i++){
      cin >> tmp;
      v.push_back(tmp);
   }
   segmentTree tree = segmentTree(v);
   cin>> Q;
   tree.st_build(1, 0, (int)v.size()-1);
   while(Q--){
      cin>>i>>j;
      inx = tree.st_rmq(i, j);
      ans = v[inx];
      cout<< ans << " ";
   }
   return 0;
 }

1 respuesta 1

2

La siguiente línea, en el método st_rmq, debería representar que el segmento que estás procesando está completamente dentro del rango.

if (L >= i && R >= j) return t[vertex];

Sin embargo, debería ser así:

if (L >= i && R <= j) return t[vertex];
1
  • Muchas gracias!! Commented el 27 feb. 2021 a las 2:56

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.