Entrevista de código: ¿Cómo usarías un árbol de Li Chao para consultas dinámicas de mínimo de líneas?

Problema y contexto

Un servicio en línea recibe líneas y = m x + b en un orden de inserción arbitrario y debe devolver el valor mínimo en un punto de consulta entero x. Los puntos de consulta también son arbitrarios. Una extensión puede restringir una línea a un intervalo [l, r] o solicitar valores máximos en su lugar.

Este problema evalúa la optimización de programación dinámica, los invariantes de divide y vencerás y la implementación de árboles de segmentos (segment trees). Una respuesta sólida primero establece si el dominio de consulta es discreto y acotado, y luego explica por qué cada nodo puede retener una línea que gana en algún lugar mientras cualquier candidato restante se envía a exactamente un hijo.

Qué evalúa el entrevistador

• Deducir el cuello de botella de escanear cada línea en O(number_of_lines) por consulta.
• Comprender la comparación en el punto medio, el intercambio y el invariante de recursión.
• Manejar pendientes arbitrarias, líneas duplicadas, coordenadas negativas y desbordamientos (overflow).
• Distinguir entre dominios enteros discretos, dominios continuos y líneas restringidas a segmentos.
• Dar las cotas de inserción/consulta de O(log C) y de inserción de segmentos de O(log^2 C).
• Explicar cuándo las pendientes monótonas y las consultas monótonas hacen que un truco de la envolvente convexa estándar sea más simple.

Aclaraciones que conviene hacer primero

1. ¿Los puntos de consulta son enteros o reales? ¿El dominio es fijo [L, R] o se expande dinámicamente? Esto determina la profundidad y la compresión de coordenadas.
2. ¿La operación es de mínimo o de máximo? ¿Se permite un conjunto vacío y qué centinela no puede colisionar con una respuesta real?
3. ¿Cuáles son las magnitudes máximas de las pendientes, los interceptos y las respuestas? ¿Se requiere un tipo de entero más amplio o multiplicación con verificación?
4. ¿Una línea se aplica solo en [l, r]? La inserción de intervalos distribuye una línea a varios nodos del árbol.
5. ¿Las pendientes de inserción o los puntos de consulta son monótonos? Si es así, un truco de la envolvente convexa basado en deque puede utilizar constantes más pequeñas.

Estructura de respuesta en 30 segundos

Construyo un dominio de árbol de segmentos [L, R] y almaceno una línea candidata en cada nodo. Al insertar una nueva línea, la comparo con la línea del nodo en los extremos y en el punto medio. Si la nueva línea gana en el punto medio, la intercambio en el nodo. La línea desplazada aún puede ganar solo en la mitad izquierda o derecha, por lo que aplico recursión en un solo hijo. Una consulta de punto evalúa cada línea en su ruta de la raíz a la hoja y toma el mínimo. Con una longitud de dominio C, la inserción y la consulta son O(log C); restringir una línea a un intervalo cuesta O(log^2 C). Las consultas de máximo invierten el comparador.

Análisis detallado paso a paso

1. Fuerza bruta y el cuello de botella

Mantén una lista de líneas y evalúa cada m x + b para cada consulta. Esto cuesta O(number_of_lines) por consulta. En una transición de programación dinámica, las inserciones y las consultas se intercalan, por lo que ni las pendientes ni los puntos de consulta se pueden ordenar sin cambiar el problema. La estructura de datos debe distribuir las comparaciones sobre el dominio de valores.

2. El invariante del nodo

Un nodo representa un intervalo cerrado [lo, hi] y almacena una línea cur. Entre las líneas que aún no se han empujado a los hijos, cur no es peor en al menos una posición candidata en este intervalo. Cualquier otra línea que aún pueda volverse óptima solo puede hacerlo en el hijo izquierdo o derecho. En una hoja, el nodo solo necesita la línea que es mejor en un punto.

3. Intercambio en el punto medio y dirección de recursión

Sea nw la nueva línea, cur la línea del nodo y mid el punto medio. Si el valor de la nueva línea en mid es menor, intercámbialas para que el nodo conserve a la ganadora del punto medio. Después del intercambio, compara qué línea gana en lo. Si la línea desplazada gana en el extremo izquierdo, solo puede reaparecer en la mitad izquierda; de lo contrario, compara el extremo derecho y aplica recursión hacia la derecha. La diferencia de dos líneas es lineal, por lo que su orden cambia a lo sumo una vez.

add(node, lo, hi, nw):
  mid = (lo + hi) // 2
  left = nw(lo) < cur(lo)
  middle = nw(mid) < cur(mid)
  if middle: swap(nw, cur)
  if lo == hi: return
  if left != middle: add(leftChild, lo, mid, nw)
  else: add(rightChild, mid + 1, hi, nw)

Utiliza una fórmula segura para el punto medio. Si m * x + b puede exceder el rango de 64 bits, utiliza un tipo más amplio, aritmética con verificación o una política explícita de saturación.

4. Consultar la ruta de la raíz a la hoja

Para el punto x, avanza recursivamente hacia la hoja que contiene x, evalúa la línea almacenada en x en cada nodo visitado y devuelve el mínimo. Los otros subárboles no contienen el punto. Un árbol implícito asigna nodos solo en las rutas tocadas por inserciones; un nodo vacío devuelve un centinela de infinito positivo.

5. Insertar una línea restringida a un intervalo

Si una línea es válida solo en [ql, qr], descompón ese intervalo con un árbol de segmentos estándar. Inserta la línea una vez en cada nodo completamente cubierto y aplica recursión para la cobertura parcial. La descomposición toca O(log C) nodos y cada inserción de Li Chao cuesta O(log C), lo que da O(log^2 C); la consulta de punto sigue siendo O(log C).

6. Coordenadas discretas y consultas continuas

Si las consultas provienen de un conjunto finito conocido, ordena y desduplica los valores de x y usa sus índices como hojas. Esto evita construir un dominio vacío enorme. Para consultas con valores reales, establece la precisión y las condiciones de parada explícitamente. La demostración para dominios enteros no se aplica automáticamente a un dominio continuo no acotado; acota el intervalo y define la tolerancia de comparación de punto flotante.

7. Compensaciones y pruebas

Cuando las pendientes y los puntos de consulta son ambos monótonos, un truco de la envolvente convexa basado en deque tiene constantes más pequeñas. Li Chao es más robusto para un orden arbitrario, a costa de más nodos y recursión. Prueba un conjunto vacío, un dominio de un solo punto, pendientes duplicadas, líneas idénticas, coordenadas negativas, una intersección en el punto medio, una línea que cubre un extremo, productos grandes y consultas de máximo; compara cada resultado con la evaluación por fuerza bruta.

Respuesta modelo de alta calidad

Primero confirmaría si el dominio de consulta es un intervalo entero acotado o si necesita compresión de coordenadas. Para [L, R], construyo un árbol de Li Chao cuyos nodos almacenan líneas candidatas. La inserción compara los extremos y el punto medio; la ganadora del punto medio se queda en el nodo y la otra línea recursa en la mitad donde las dos líneas pueden cambiar de orden. Su diferencia es lineal, por lo que la línea desplazada no puede mejorar en dos direcciones separadas. Una consulta de punto toma el mínimo a lo largo de una ruta de la raíz a la hoja, lo que da O(log C) para inserción y consulta. Si las pendientes y las consultas son monótonas, usaría un truco de la envolvente convexa; las líneas restringidas a intervalos requieren descomposición en segmentos e inserción en O(log^2 C).

Errores comunes

• Comparar solo el punto medio y detenerse → la otra línea puede ganar en un extremo → utiliza comparaciones de extremos y punto medio para elegir un hijo.
• Asumir que las pendientes deben ser monótonas → la inserción arbitraria produce respuestas incorrectas → utiliza el invariante de intervalo de Li Chao o establece la condición previa de la envolvente convexa.
• Calcular m * x + b con aritmética de 64 bits sin verificación → el desbordamiento altera las comparaciones → utiliza aritmética más amplia o con verificación.
• Permitir un dominio dinámico no acotado → la recursión no tiene terminación → acota el dominio entero, comprime coordenadas o define precisión de punto flotante.
• Copiar una línea de intervalo en cada hoja → la complejidad se degenera → descompón el intervalo e inserta en nodos completamente cubiertos.
• Devolver cero para un nodo vacío → un mínimo se reduce incorrectamente → utiliza un centinela de infinito positivo fuera del rango de respuesta.

Preguntas de seguimiento y respuestas

¿Qué cambia para consultas de máximo?

Invierte cada comparación, o niega tanto m como b, resuelve una consulta de mínimo y niega el resultado. La semántica de conjunto vacío y de desbordamiento debe invertirse de manera coherente en lugar de cambiar solo el valor de retorno final.

¿Puede un árbol basado en arreglos manejar un dominio de 10 a la 18?

No preasignando cada nodo. Utiliza un árbol implícito que cree nodos solo a lo largo de las rutas de inserción; la profundidad es aproximadamente el número de bits del dominio. Si las coordenadas de consulta son finitas, la compresión de coordenadas suele ahorrar más memoria.

Dos líneas empatan en el punto medio. ¿Cómo evitas una rama incorrecta?

Elige una regla de desempate determinista, como conservar la línea anterior o preferir un orden de pendiente. Utiliza desigualdades estrictas de manera coherente en los extremos y en el punto medio para que las líneas idénticas no apliquen recursión infinitamente.

¿Por qué basta con un solo lado recursivo?

La diferencia de dos líneas es lineal y tiene a lo sumo un cero. Después de conservar la ganadora del punto medio, la línea desplazada solo puede recuperarse hacia un extremo donde el orden difiere, seleccionando unívocamente el hijo izquierdo o el derecho.

¿Cuándo es mejor un truco de la envolvente convexa?

Si las líneas llegan en orden de pendiente monótono y las consultas son monótonas, un deque de envolvente puede proporcionar consultas amortizadas en O(1) o consultas por búsqueda binaria en O(log n) con menos memoria. El orden arbitrario, o las líneas restringidas a segmentos, favorece la generalidad de Li Chao.