Los arrays diferenciales constituyen una técnica esencial para optimizar operaciones de actualización por rangos en secuencias. Esta estrategia se basa en construir un array auxiliar que, mediante sumas prefijadas, permite reconstruir el array original de manera eficiente tras múltiples modificaciones.

Fundamentos de los Arrays Diferenciales

Dado un array a de longitud n, se define un array diferencial b donde cada elemento b[i] representa la diferencia a[i] - a[i-1], considerando a[0] = 0. Al calcular la suma prefijada de b, se recupera el array a, ya que las diferencias se cancelan sucesivamente.

Aplicación en Actualizaciones por Rango Unidimensional

Para realizar una operación de incremento por x en un rango [l, r], se actualizan dos posiciones en el array diferencial: b[l] += x y b[r+1] -= x. Esto garantiza que el efecto del incremento se anule a partir de r+1. Tras todas las operaciones, se calcula la suma prefijada de b para obtener el array final.

El código siguiente ilustra esta técnica, empleando variables renombradas y comentarios en español para mayor claridad:

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int longitud, consultas;
    cin >> longitud >> consultas;
    int arreglo[5000005], diferencias[5000005];
    for (int i = 1; i <= longitud; ++i) {
        cin >> arreglo[i];
    }
    // Inicializar array diferencial
    for (int i = 0; i <= longitud; ++i) {
        diferencias[i] = 0;
    }
    // Procesar consultas de actualización por rango
    while (consultas--) {
        int inicio, fin, valor;
        cin >> inicio >> fin >> valor;
        diferencias[inicio] += valor;
        diferencias[fin + 1] -= valor;
    }
    // Reconstruir array y encontrar mínimo
    int minimo = 1000000000; // Un valor grande inicial
    for (int i = 1; i <= longitud; ++i) {
        diferencias[i] += diferencias[i - 1];
        arreglo[i] += diferencias[i];
        minimo = min(minimo, arreglo[i]);
    }
    cout << minimo << endl;
    return 0;
}

La complejidad temporal para cada actualización es O(1), mientras que la reconstrucción completa toma O(n).

Extensión a Dos Dimensiones

En matrices, el array diferencial se aplica para actualizar subrectángulos. Para incrementar por x el área definida por (x1, y1) hasta (x2, y2), se modifican cuatro posiciones en el array diferencial 2D: b[x1][y1] += x, b[x1][y2+1] -= x, b[x2+1][y1] -= x, y b[x2+1][y2+1] += x. Esto compensa el efecto fuera del rango deseado.

Una implemnetación básica en código podría estructurarse así:

void actualizarRango2D(int x1, int y1, int x2, int y2, int valor, int diff[100][100]) {
    diff[x1][y1] += valor;
    diff[x1][y2 + 1] -= valor;
    diff[x2 + 1][y1] -= valor;
    diff[x2 + 1][y2 + 1] += valor;
}

Este método permite manejar actualizaciones en matrices de manera eficiente, con complejidad constante por operación.

Diferenciales en Árboles

Para grafos en forma de árbol, se emplea el diferencial para actualizar rutas entre nodos. Dados dos nodos u y v, se incrementan sus valores en el array diferencial b por z. Luego, se descuenta z en el ancestro común más bajo (LCA) y en su padre para evitar sobreactualizaciones. La fórmula es: b[u] += z, b[v] += z, b[lca(u, v)] -= z, y b[padre[lca(u, v)]] -= z.

Un ejemplo de función para esta operación:

// Suponiendo que lca() calcula el ancestro común más bajo y padre[] almacena padres
void diferencialArbol(int u, int v, int z, int b[], int padre[], int (*lca)(int, int)) {
    b[u] += z;
    b[v] += z;
    int ancestro = lca(u, v);
    b[ancestro] -= z;
    b[padre[ancestro]] -= z;
}

Esta técnica es particularmente útil en problemas de programación competitiva que involucran actualizaciones en rutas de árboles, ofreciendo una alternativa a estructuras más complejas como segment trees.

Los arrays diferenciales destacan por su simplicidad y bajo riesgo de errores, siendo ideales en escenarios donde las consultas son acumulativas o se prefieren implementaciones concisas. Aunque existen estructuras de datos más versátiles, su eficiencia en actualizaciones por rango los convierte en una herramienta valiosa en el diseño de algoritmos.