Fusión de Árboles de Segmentos

La fusión de árboles de segmentos es una técnica frecuentemente utilizada en problemas sobre árboles, ya que el proceso de fusión conserva la estructura jerárquica natural del árbol. Se aplica comúnmente junto con árboles de segmentos de valores (权值线段树) con asignación dinámica de nodos.

Concepto

La idea consiste en construir un nuevo árbol de segmentos donde cada nodo resulta de combinar los nodos correspondientes de dos árboles originales. Dado que reconstruir un árbol completo sería prohibitivo en memoria, se aprovecha la asignación dinámica de nodos para crear únicamente los nodos necesarios.

Existen dos enfoques:

• Fusionar un árbol directamente sobre otro existente, reutilizando su estructura.
• Crear un árbol completamente nuevo a partir de ambos.

El primer enfoque es preferible cuando uno de los árboles ya no se necesita tras la fusión, ya que reduce el consumo de memoria y simplifica la implementación.

Procedimiento

Sean dos árboles A y B. Se recorre recursivamente desde el nodo raíz:

• Si alguno de los nodos correspondientes no existe, se devuelve directamente el nodo del otro árbol.
• Si ambos existen y se llega a una hoja, se combina la información almacenada.
• En caso contrario, se desciende recursivamente por ambos hijos y se actualiza el nodo actual.

void combinar(int &nodoA, int nodoB, int lo, int hi) {
    if (!nodoA || !nodoB) {
        nodoA |= nodoB;
        return;
    }
    if (lo == hi) {
        // combinar la información específica de las hojas
        return;
    }
    int mid = (lo + hi) >> 1;
    combinar(hijoIzq[nodoA], hijoIzq[nodoB], lo, mid);
    combinar(hijoDer[nodoA], hijoDer[nodoB], mid + 1, hi);
    actualizar(nodoA);
}

Complejidad

Para dos árboles completos, la operación tiene una complejidad de O(n log n). En la práctica, como se usan árboles de valores cuyo total de nodos es del orden de n, y no se repiten fusiones sobre el mismo árbol, el número de nodos nuevos creados es del orden de n log n, resultando en una complejidad total de O(n log n).

Ejemplo: Rainy Tail (P4556)

El problema consiste en procesar consultas de adición sobre caminos en un árbol y determinar, para cada nodo, qué tipo de recurso aparece con mayor frecuencia.

La estrategia consiste en aplicar diferenciales sobre el árbol: cada consulta de ruta se descompone en dos modificaciones puntuales. Para cada nodo se mantiene un árbol de segmentos de valores que registra cuántos recursos de cada tipo llegan a ese nodo. Finalmente, un recorrido DFS bottom-up fusiona los árboles de los hijos en el árbol del padre.

En cuanto al tamaño del arreglo de nodos: cada modificación diferencial crea hasta O(log n) nodos nuevos, hay 4 modificaciones por consulta y m consultas, por lo que reservar aproximadamente n × 70 nodos es suficiente.

División de Árboles de Segmentos

La división es la operación inversa a la fusión. Solo tiene sentido sobre secuencias ordenadas y se aplica con menor frecuencia.

Procedimiento

El objetivo es separar el intervalo [l, r] de un árbol existente con dominio [1, N] y construir un nuevo árbol con esa porción.

• Se recorre recursivamente desde la raíz. Si el nodo no existe o su intervalo [lo, hi] no intersecta [l, r], se retorna sin hacer nada.
• Si hay intersección, se crea un nuevo nodo.
• Si [l, r] contiene completamente [lo, hi], se transfiere el nodo actual al nuevo árbol y se desconecta del árbol original.

int dividir(int l, int r, int lo, int hi, int &nodo) {
    int nuevoNodo = ++totalNodos;
    if (l <= lo && hi <= r) {
        datos[nuevoNodo] = datos[nodo];
        nodo = 0;
    } else {
        int mid = (lo + hi) >> 1;
        if (l <= mid)
            izq[nuevoNodo] = dividir(l, r, lo, mid, izq[nodo]);
        if (r > mid)
            der[nuevoNodo] = dividir(l, r, mid + 1, hi, der[nodo]);
        recalcular(nodo);
        recalcular(nuevoNodo);
    }
    return nuevoNodo;
}

Complejidad

La estructura de la recursión es análoga a la de una modificación por intervalo, por lo que la complejidad es O(log n).

Ejemplo: P5494

Este problema combina fusión y división junto con modificaciones puntuales, consultas de rango y búsqueda del k-ésimo menor global. El aálisis de espacio: cada modificación puntual genera O(log n) nodos y cada división genera aproximadamente 2 log n nodos; como por consulta se ejecuta una sola operación, reservar 2m log n nodos (aproximadamente n × 40) es suficiente. Hay que evitar usar long long globalmente para no exceder la memoria.

Línea de Barrido (Scan Line)

La técnica de línea de barrido consiste en desplazar una recta (horizontal o vertical) a través del plano para resolver problemas de área, perímetro o conteo de puntos en dos dimensiones.

Problema clásico: P5490

Dado n rectángulos en el plano por sus esquinas opuestas, calcular el área total de la unión de todos los rectángulos.

La idea central es que si se desplaza una línea vertical de izquierda a derecha, la longitud cubierta por la unión de rectángulos sobre esa línea solo cambia en las coordenadas x donde comienza o termina un rectángulo. Esto divide el plano en 2n franjas verticales; en cada franja, la longitud cubierta es constante, y el área de esa franja es longitud × ancho.

Algoritmo

Se extraen los bordes izquierdo y derecho de cada rectángulo. Para un rectángulo con esquinas (x1, y1) y (x2, y2), el borde izquierdo se representa como (x1, y1, y2, +1) y el derecho como (x2, y1, y2, -1). Se ordanan los 2n eventos por x creciente.

Dado que los valores de y pueden llegar a 10^9 pero solo hay 2×10^5 de ellos, se aplica discretización. Tras discretizar, si hay m valores distintos de y, la línea de barrido se divide en m-1 segmentos.

Árbol de segmentos discreto

Un aspecto crucial es que los eventos definen coordenadas (puntos), pero lo que se debe mantener es cuántas veces está cubierto cada segmento entre dos coordenadas consecutivas. Por ello, el árbol de segmentos trabaja con intervalos en lugar de puntos: la división del árbol es [lo, mid] y [mid, hi] (no [mid+1, hi]), y los nodos hoja representan intervalos de ancho 2.

Cada nodo del árbol almacena:

• Los valores discretos originales de los extremos del intervalo.
• cubrimiento: número de rectángulos que cubren completamente este intervalo.
• longitud: la longitud total cubierta dentro de este intervalo.

Como las modificaciones siempre vienen en pares (+1 y -1), no se necesitan lazy marks: el contador nunca se vuelve negativo de forma problemática.

void recalcular(int idx) {
    if (cobertura[idx] > 0) {
        longitud[idx] = coordOrig[limSup[idx]] - coordOrig[limInf[idx]];
    } else {
        longitud[idx] = longitud[hijoIzq[idx]] + longitud[hijoDer[idx]];
    }
}

void actualizar(int idx, int yLo, int yHi, int delta) {
    if (yHi <= limInf[idx] || limSup[idx] <= yLo) return;
    if (yLo <= limInf[idx] && limSup[idx] <= yHi) {
        cobertura[idx] += delta;
        recalcular(idx);
        return;
    }
    actualizar(hijoIzq[idx], yLo, yHi, delta);
    actualizar(hijoDer[idx], yLo, yHi, delta);
    recalcular(idx);
}

La función de actualización funciona así: si no hay intersección, se retorna inmediatamente; si el intervalo del nodo está completamente contenido, se ajusta el contador y se recalcula; si hay intersección parcial, se desciende a los hijos. En la función de recálculo, si el contador es positivo, la longitud cubierta es la del intervalo completo; si es cero, se suman las longitudes de los hijos.

Con el árbol de segmentos discreto, cada modificación pasa de O(n) a O(log n), y la complejidad total del algoritmo es O(n log n).

Un detalle importante de implementación: como la línea longitud[idx] = longitud[hijoIzq[idx]] + longitud[hijoDer[idx]] puede acceder a hijos de nodos hoja, conviene reservar 8 veces el espacio para evitar errores de acceso fuera de límites.