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;
}