Consigna y contexto
Implementa una estructura de arreglo de enteros con historial. Cada actualización modifica una posición, y una consulta puede pedir la suma de un intervalo cerrado en cualquier versión anterior. Las versiones antiguas deben permanecer inmutables. Explica los límites de coordenadas, la complejidad temporal y espacial, las versiones ramificadas y las pruebas.
Esta es una pregunta difícil sobre estructuras de datos que abarca divide y vencerás, uso compartido de estructuras, actualizaciones inmutables, límites y pruebas de complejidad. Asume una longitud de arreglo fija, actualizaciones por asignación de puntos y sumas de rango en intervalos cerrados [l, r]. Las actualizaciones de rango, la eliminación o la fusión de versiones son extensiones independientes y deben mencionarse antes de implementarse.
Qué evalúa el entrevistador
El entrevistador quiere que aclares que la persistencia permite consultar raíces antiguas; no copia todo el árbol en cada actualización. Una implementación sólida crea nuevos nodos a lo largo del camino de actualización, reutiliza los subárboles no modificados y almacena una raíz por versión. También establece la convención de intervalos, el comportamiento ante consultas vacías, la numeración de versiones, los valores negativos, los límites y el límite de espacio.
Preguntas para aclarar primero
- ¿La longitud del arreglo y el universo de coordenadas son fijos, o se pueden comprimir las coordenadas primero?
- ¿Una actualización es una asignación o un incremento, y se puede actualizar la misma posición repetidamente?
- ¿Los rangos son cerrados o semiabiertos, y qué debe devolver un rango vacío?
- ¿Una versión puede ramificarse desde cualquier raíz antigua, o solo agregarse desde la versión más reciente?
- ¿Se requiere seguridad en hilos (thread safety), persistencia en disco o uso compartido entre procesos?
- ¿Necesitamos sumas exactas de enteros, comprobaciones de desbordamiento o enteros grandes?
- ¿Cuáles son los límites de versiones y de operaciones totales?
Estructura de respuesta en 30 segundos
“Representaría cada versión mediante la raíz de un segment tree inmutable. Una actualización de punto copia O(log n) nodos desde la raíz hasta la hoja, comparte cada subárbol hermano intacto, y una consulta desciende desde la raíz solicitada, devolviendo la suma del nodo cuando hay cobertura total. Un arreglo de raíces permite ramificarse desde cualquier versión anterior. La construcción toma O(n); cada actualización y consulta toma O(log n); el espacio total es el árbol inicial más O(log n) nuevos nodos por actualización. Haría pruebas con bifurcaciones, casos límite, valores negativos y pruebas diferenciales aleatorias”.
Respuesta paso a paso
Establece primero el invariante: un nodo cubre un intervalo cerrado específico [lo, hi], sum es la suma de ese intervalo en su versión, una hoja cubre una posición, la suma de un nodo interno es igual a la suma de sus hijos y un nodo nunca se muta después de su creación. Cada versión almacena un puntero a su raíz.
Para los índices del arreglo 0..n-1, construye recursivamente. Si la entrada utiliza coordenadas enteras grandes y dispersas, recopila las coordenadas posibles y comprímelas antes de construir; no materialices un universo de coordenadas gigantesco.
El siguiente pseudocódigo utiliza actualizaciones por asignación y consultas de intervalos cerrados:
Node { left, right, sum }
build(lo, hi, values):
if lo == hi: return Node(null, null, values[lo])
mid = floor((lo + hi) / 2)
left = build(lo, mid, values)
right = build(mid + 1, hi, values)
return Node(left, right, left.sum + right.sum)
set(node, lo, hi, index, value):
if lo == hi: return Node(null, null, value)
mid = floor((lo + hi) / 2)
if index <= mid:
nextLeft = set(node.left, lo, mid, index, value)
nextRight = node.right
else:
nextLeft = node.left
nextRight = set(node.right, mid + 1, hi, index, value)
return Node(nextLeft, nextRight, nextLeft.sum + nextRight.sum)
sum(node, lo, hi, ql, qr):
if qr < lo or hi < ql: return 0
if ql <= lo and hi <= qr: return node.sum
mid = floor((lo + hi) / 2)
return sum(node.left, lo, mid, ql, qr)
+ sum(node.right, mid + 1, hi, ql, qr)roots[0] almacena el árbol inicial. Para actualizar la posición i desde la versión base, crea roots[next] = set(roots[base], 0, n - 1, i, value). El grafo de versiones es una estructura dirigida acíclica compartida referenciada por raíces, no una cadena de historial lineal. Ramificar significa elegir cualquier raíz antigua como entrada para la actualización.
Maneja los límites de forma explícita: para n == 0, no crees una raíz; los índices fuera de rango y ql > qr deben devolver un error estructurado o seguir el contrato establecido; recortar una consulta no debe ocultar silenciosamente un error del invocador. Evita el desbordamiento de lo + hi calculando lo + floor((hi - lo) / 2) cuando los límites enteros puedan ser grandes.
La construcción inicial utiliza O(n) nodos y tiempo. Una actualización de punto copia un camino de la raíz a la hoja, por lo que crea O(log n) nodos; una consulta de rango visita O(log n) segmentos canónicos y toma O(log n) tiempo. Después de u actualizaciones, el espacio total es O(n + u log n), no O(nu). La asignación o suma de rango también puede usar copiado de caminos, pero las etiquetas perezosas (lazy tags), las combinaciones de nodos y los límites de espacio cambian.
La inmutabilidad es el límite de la corrección. Nunca modifiques el sum ni el puntero a un hijo de un nodo antiguo durante una actualización. El recolector de basura o el conteo de referencias pueden reclamar nodos; la liberación manual debe saber qué raíces de versiones siguen activas, ya que eliminar una versión no puede liberar nodos que aún comparte otra.
Si solo importa la versión más reciente, un segment tree normal es más simple. La persistencia vale la pena para consultas históricas, reversiones (rollback), experimentos con ramificaciones o viajes en el tiempo. Para operaciones totalmente fuera de línea (offline), un método de prefijos o de barrido (sweep-line) offline puede ser más simple; conecta la elección de la estructura de datos con la carga de trabajo de las consultas.
Comienza las pruebas con arreglos pequeños. Después de cada actualización, copia un arreglo plano y compara versiones y rangos aleatorios con la estructura persistente. Cubre ramificaciones desde la versión 0, actualizaciones repetidas en una misma posición, números negativos, un solo elemento, rangos completos, puntos individuales, rangos vacíos y ambos límites. Verifica también el uso compartido: después de actualizar una posición, el subárbol no modificado debe mantener la misma identidad de objeto.
Prueba la inmutabilidad directamente. Guarda todos los resultados de consultas de versiones antiguas, realiza varias actualizaciones con ramificaciones y consulta las raíces antiguas nuevamente; cualquier cambio significa que un nodo antiguo fue mutado. Para cargas de trabajo grandes, cuenta los nodos asignados y confirma que el crecimiento esté cerca del O(n) inicial más O(log n) por actualización en lugar de copias accidentales de todo el árbol.
Respuesta de ejemplo de alta calidad
“Asumiré un arreglo de longitud fija, actualizaciones por asignación de puntos, sumas de intervalos cerrados y ramificaciones desde cualquier versión antigua. Cada nodo cubre [lo, hi] y almacena su suma; los nodos son inmutables después de su construcción. roots[v] almacena la raíz para la versión v.
Construyo recursivamente. Al actualizar, copio el camino hasta la hoja de destino: creo un nuevo hijo en el lado de destino, reutilizo el puntero antiguo en el otro lado y creo cada nuevo padre a partir de las sumas de sus hijos. Consulto desde la raíz solicitada; devuelvo cero si no hay solapamiento, la suma del nodo en caso de cobertura total, y de lo contrario hago recursión.
La construcción toma O(n) en tiempo y espacio. Cada actualización crea O(log n) nodos, y tanto la actualización como la consulta toman O(log n); después de u actualizaciones, el espacio total es O(n + u log n). Las raíces antiguas siguen apuntando a los nodos antiguos, por lo que las versiones históricas no pueden contaminarse. Comprimiría primero un universo de coordenadas grande; para actualizaciones de rango, reevaluaría las etiquetas perezosas y el espacio.
Probaría bifurcaciones desde la versión 0, actualizaciones repetidas, negativos, rangos vacíos y cada límite contra un oráculo de arreglo plano. Verificaría que los subárboles no modificados se compartan y que las consultas antiguas permanezcan sin cambios después de nuevas actualizaciones. Si solo se necesita el valor más reciente, usaría un segment tree regular y solo asumiría el costo de la persistencia cuando el historial o la reversión sean un requisito real”.
Errores comunes
- Copiar todo el árbol → cada actualización pasa a ocupar O(n) de espacio → copiar solo el camino de la raíz a la hoja.
- Mutar un nodo antiguo y guardar una nueva raíz → todas las versiones antiguas que lo comparten cambian → mantener los nodos inmutables.
- Tratar las versiones como una cadena lineal → no se puede experimentar ni revertir desde una raíz arbitraria → permitir que el arreglo de raíces se ramifique.
- Dejar implícita la convención de intervalos → los rangos cerrados y semiabiertos generan errores de límites → fijar una convención en los invariantes y firmas.
- Materializar coordenadas gigantescas → el universo puede empequeñecer los puntos reales → comprimir coordenadas o usar nodos dinámicos.
- Afirmar un espacio total de O(n) → cada actualización agrega nodos del camino → especificar O(n + u log n).
- Liberar nodos recursivamente al eliminar una versión → otra versión puede seguir compartiéndolos → usar conteo de referencias o recolección de basura.
Preguntas de seguimiento y respuestas
Pregunta de seguimiento 1: ¿La estructura sigue funcionando para sumas por rangos?
Se aplica copiado de caminos a los nodos tocados por la actualización y se copia cada camino relevante. Si se usan etiquetas perezosas (lazy tags), la etiqueta pertenece a un nodo nuevo y nunca debe escribirse en un nodo compartido. La cantidad de nodos nuevos puede variar de O(log n) a O(log n más nodos cubiertos), por lo que se deben indicar los límites para la implementación real en lugar de reutilizar la afirmación de la actualización de punto.
Pregunta de seguimiento 2: ¿Cómo consultarías la diferencia entre dos versiones?
Recorriendo ambas raíces juntas. Si los punteros de los nodos son idénticos, ese subárbol no ha cambiado y se puede omitir. De lo contrario, se desciende o se calcula una diferencia agregada. Reportar cada posición modificada también depende del tamaño de la salida.
Pregunta de seguimiento 3: ¿Por qué no copiar el arreglo y construir una suma de prefijos cada vez?
Copiar el arreglo cuesta O(n) de tiempo y espacio por actualización. Con pocas versiones y un arreglo pequeño, ese método más simple puede ser mejor; la persistencia cambia O(log n) de nuevo espacio para permitir muchas versiones, consultas históricas en línea y actualizaciones locales.
Pregunta de seguimiento 4: ¿Cómo persistes las raíces de las versiones en disco?
Asignando identificadores estables a los nodos, almacenando identificadores de hijos en lugar de punteros de memoria y persistiendo una tabla de versión a raíz. Usando anexado (append) o copia en escritura (copy-on-write) y asegurando que los nuevos nodos sean duraderos antes de publicar la raíz. En la recuperación, validando las referencias y la tabla de raíces; nunca serializando direcciones de memoria sin procesar.
Pregunta de seguimiento 5: ¿Cómo demuestras que una versión antigua no está contaminada?
Por inducción sobre las actualizaciones: solo se crean nodos nuevos, no cambia ningún campo de los nodos antiguos y el nuevo árbol referencia subárboles antiguos no modificados más un camino nuevo. Por lo tanto, los nodos alcanzables desde una raíz antigua y sus valores permanecen inalterados. Las pruebas diferenciales aleatorias con ramificaciones validan el invariante en la práctica.