El árbol de segmentos, como otras estructuras de datos arborescentes, puede implementarse definiendo una clase “Nodo” donde se guarde la información de cada nodo y punteros a sus hijos, pero existe una forma de implementarlo más sencilla. La idea importante es la siguiente: la información se guarda en un array y cada nodo tiene una posición correspondiente donde está guardada su información. La posición 1 corresponde a la raíz del árbol y, si a un nodo le corresponde la posición i, entonces a su hijo izquierdo le corresponde la posición 2*i y a su hijo derecho le corresponde la posición 2*i+1. (A cada posición le corresponde un único nodo de esta forma)
Aquí está el código de una posible implementación del árbol de segmentos para RMQ que vimos en el anterior manual:
vector<int> st; //vector que contiene la información del segment tree
vector<int> a; //vector que contiene la secuencia sobre la que se construye el arbol
//Construye el subárbol con nodo de posición p, correspondiente al subintervalo [l, r]
void build(int p, int l, int r) {
if(l == r) {
st[p] = l;
}
else {
build(2*p, l, (l+r)/2);
build(2*p+1, (l+r)/2+1, r);
int i1 = st[2*p];
int i2 = st[2*p+1]
if(a[i1] < a[i2]) st[p] = i1;
else st[p] = i2;
}
}
//Responde la RMQ sobre el intervalo [i, j] usando el subarbol con nodo de posición p, correspondiente al intervalo [l, r]
int rmq(int p, int l, int r, int i, int j) {
if(l > j or r < i) return -1;
if(l >= i and r <= j) return st[p];
int i1 = rmq(2*p, l, (l+r)/2, i, j);
int i2 = rmq(2*p+1, (l+r)/2+1, r, i, j);
if(i1 == -1) return i2;
if(i2 == -1) return i1;
if(a[i1] < a[i2]) return i1;
else return i2;
}
Expliquemos primero la función build, que es la que construirá el árbol de segmentos a partir de nuestro vector. Esta función debe ser llamada como build(1, 0, n-1), con el vector st previamente inicializado con un tamaño de 4*n, donde n es el tamaño del vector a.
¿Por qué un tamaño de $4n$? En el manual anterior, hemos trabajado con un vector de tamaño $8$, que es una potencia de $2$, por lo que se generaba un árbol binario perfectamente “equilibrado” de tamaño $15$. En general, para un vector de longitud potencia de $2$ se forma un árbol binario equilibrado con $2n-1$ nodos, así que como estamos empezando a indizar por $1$, se necesita un vector de tamaño $2n$. Pero también podemos crear un árbol de segmentos sobre un vector cuyo tamaño no sea una potencia de dos: en este caso, a veces cuando dividimos en dos los segmentos para crear los nodos de los hijos un segmento tendrá mayor longitud que otro, y esto acabará causando que el árbol no esté completamente balanceado, es decir, que algunas hojas (los nodos correspondientes a un intervalo de longitud $1$) estarán a una profundidad mayor que otras. El número de nodos total seguirá siendo $2n-1$, pero debido a cómo hemos numerado los nodos, es posible que las posiciones de algunos nodos sean mayores que el número total de nodos (es decir, que se “salten” algunas posiciones) y por tanto $2n$ de tamaño no sea suficiente. Se puede ver que la profundidad del árbol es como máximo $\lceil \log_2 n\rceil$ y por tanto $4n$ es mayor que cualquier posición.
La función build se llama recursivamente para construir los dos subárboles correspondientes a los dos hijos del árbol actual. Esta recursión para cuando se llega a un subárbol de un solo nodo, en cuyo caso el valor correspondiente al nodo es el índice del elemento correspondiente. Una vez están construidos los dos subárboles, el valor correspondiente al nodo es el índice con mínimo valor entre los índices de los dos hijos.
La función rmq se va llamando recursivamente para acabar reportando sólo los valores relevantes dentro del subintervalo $[i, j]$. Como lo hemos implementado es un poco diferente a como lo explicamos en el manual anterior: aquí, en lugar de consultar sólo el subárbol relevante, se hacen las dos llamadas a los dos subárboles y, en el caso de que un subárbol corresponda a un intervalo que está fuera del intervalo de consulta, se retorna -1 (primera línea de la función), indicando que esa consulta es inválida. Por eso, cuando decidimos qué valor retornar, hay que tener en cuenta los casos en los que alguno de los valores devueltos por las llamadas recursivas es -1. Tal como explicamos en el manual anterior, la recursividad acaba cuando llegamos a un nodo cuyo intervalo está contenido en el intervalo de consulta.
Una funcionalidad adicional que se puede añadir a nuestro árbol de segmentos es la poder hacer actualizaciones del vector a. La idea importante es que, si cambiamos el valor de a[i], hay como mucho $\mathcal{O}(\log n)$ nodos del árbol de segmentos que hay que actualizar, que son los nodos cuyos intervalos contienen el índice i. Veamos la implementación:
void update(int p, int l, int r, int i) {
if(l > i or r < i) return;
if(l == r) {
st[p] = i;
}
else {
update(2*p, l, (l+r)/2, i);
update(2*p+1, (l+r)/2+1, r, i);
int i1 = st[2*p];
int i2 = st[2*p+1]
if(a[i1] < a[i2]) st[p] = i1;
else st[p] = i2;
}
}
Esta función se llama como update(1, 0, n-1, i) después de hacer la modificación pertinente a a[i]. Aquí vamos llamando recursivamente la función update, descendiendo por los nodos que contienen el índice i (aquí, como antes, lo hemos implementado de forma que se hacen las dos llamadas siempre y después se retorna cuando tenemos un intervalo que no contiene a i; se puede ver que una de las dos llamadas siempre retorna inmediatamente). Cuando llegamos a la hoja con el nodo correspondiente al intervalo $[i, i]$ la recursividad para y actualizamos el valor del nodo correspondiente: en este caso la línea st[p] = i es innecesaria ya que siempre tendremos que para nodos hoja st[p] es igual a i independientemente del valor de a[i], pero por ejemplo si estuviéramos implementando un segment tree donde guardamos valores y no índices (por ejemplo, para RSQ) tendríamos que actualizar el valor st[p] = a[i]. Después se va volviendo hacia arriba en el árbol volviendo a calcular los valores de los nodos de forma semejante a como se hizo en la función build.
Añadir nuevo comentario