Entrevista técnica: ¿Cómo construir un segment tree con propagación perezosa (lazy) para suma e incremento en rangos?

Planteamiento y alcance

Dado un arreglo de enteros de longitud n, procesa dos operaciones online: sumar delta a cada valor en el intervalo cerrado [l, r], y retornar la suma de [l, r]. El objetivo es una construcción en O(n), O(log n) por operación y O(n) de espacio extra. Especifica que los intervalos son cerrados, que delta puede ser negativo y que la persistencia queda fuera del alcance a menos que se solicite.

Qué evalúa el entrevistador

Escribe primero el invariante: tree[p] siempre es la suma real para el intervalo del nodo, mientras que lazy[p] es un incremento uniforme ya incluido en esa suma pero que aún no se ha aplicado a los hijos. Una respuesta sólida actualiza únicamente un nodo totalmente cubierto, hace push antes del recorrido parcial y multiplica el incremento por la longitud cubierta.

Aclaraciones antes de programar

1. ¿La actualización es suma, asignación o un mínimo de rango? Sus reglas de composición de etiquetas perezosas difieren.
2. ¿El agregado es una suma, mínimo o máximo? La fusión de nodos y la fórmula de la etiqueta cambian.
3. ¿Los intervalos son cerrados? Esta respuesta utiliza intervalos cerrados [l, r]; los intervalos semiabiertos requieren división y longitudes consistentes.
4. ¿Qué tan grandes pueden llegar a ser los valores? tree[p] + delta * length puede desbordar enteros de 32 bits, por lo que se debe elegir un tipo más amplio.

Solución recomendada y deducción

Almacena un árbol binario implícito en arreglos. Un nodo [lo, hi] se divide en mid en [lo, mid] y [mid+1, hi]. Para una actualización totalmente cubierta, suma delta * (hi-lo+1) a tree[p] y acumula delta en lazy[p]; los valores de los hijos pueden permanecer intactos hasta que se necesiten.

class LazySumTree:
    def __init__(self, values):
        self.n = len(values)
        self.tree = [0] * (4 * max(1, self.n))
        self.lazy = [0] * len(self.tree)
        if self.n:
            self._build(1, 0, self.n - 1, values)

    def _apply(self, p, lo, hi, delta):
        self.tree[p] += delta * (hi - lo + 1)
        self.lazy[p] += delta

    def _push(self, p, lo, hi):
        if self.lazy[p] == 0 or lo == hi:
            return
        mid = (lo + hi) // 2
        d = self.lazy[p]
        self._apply(p * 2, lo, mid, d)
        self._apply(p * 2 + 1, mid + 1, hi, d)
        self.lazy[p] = 0

Completa add y sum recursivamente con el mismo invariante: llama a _apply en cobertura total; llama a _push antes de la cobertura parcial; recalcula el padre a partir de sus hijos después de retornar. Cada nivel visita solo un número constante de nodos frontera, por lo que las actualizaciones y consultas son de O(log n) y el almacenamiento es de O(n).

Alternativas y compensaciones

Para actualizaciones puntuales más sumas de prefijos, un Fenwick tree es más corto y tiene constantes más pequeñas. Para sumas en rango offline seguidas de una única lectura final, un arreglo de diferencias es más simple. Un segment tree con propagación perezosa justifica su complejidad cuando coexisten actualizaciones en rango online y agregaciones en rango. La asignación en rango necesita una etiqueta adicional de "tiene asignación" y una regla de precedencia explícita: la asignación reemplaza una asignación anterior y una etiqueta de suma, mientras que una suma posterior se acumula después de ella.

Modos de falla, límites y contraejemplos

• Olvidar la longitud del intervalo hace que sumar 3 a [2, 5] aumente la suma en 3 en lugar de 12.
• Hacer recursión después de una cobertura total pierde la propagación perezosa y puede aplicar una actualización repetidamente.
• No limpiar una etiqueta después del push aplica el mismo incremento nuevamente en la siguiente visita.
• No recalcular un padre después de una actualización parcial deja desactualizadas las consultas posteriores de cobertura total.
• Mezclar intervalos cerrados y semiabiertos causa errores de un solo elemento o de mid+1; valida un arreglo vacío, l > r y n=0 en el límite.

Lista de verificación de pruebas y validación

Usa un arreglo ingenuo como oráculo, genera actualizaciones y consultas aleatorias y compara después de cada operación. Incluye rangos de un solo elemento, el rango completo, ambos límites, deltas negativos, solapamientos repetidos y valores todos iguales. Comprueba mediante aserciones que un padre sea igual a la suma de sus hijos después de las llamadas recursivas y verifica que el tipo de entero elegido no sufra desbordamiento con entradas grandes. Agrega una prueba de equivalencia si implementas un diseño iterativo.

Preguntas de seguimiento

¿Cómo pueden coexistir la asignación en rango y la suma en rango?

Mantén una etiqueta de asignación opcional y una etiqueta de suma por nodo. Una nueva asignación reemplaza tanto la asignación anterior como la suma; una nueva suma se acumula después de la asignación. Haz push de la asignación primero y de la suma en segundo lugar. El orden es la regla de corrección.

¿Cómo se soporta el mínimo en rango?

Almacena el mínimo del intervalo en lugar de la suma; una suma en rango sigue sumando delta a ese mínimo, por lo que la etiqueta perezosa sigue siendo simple. La operación chmin o chmax en rango requiere invariantes más ricos, como segment-tree beats.

¿Cómo se exponen las versiones históricas?

Utiliza un segment tree persistente: copia los nodos a lo largo de la ruta de actualización y comparte los subárboles no modificados. Cada actualización copia alrededor de O(log n) nodos, y un puntero a la raíz identifica una versión, por lo que el espacio crece con el número de actualizaciones.