Segment Tree

¿Qué es un Segment Tree?

Analogía: Imagina que eres director de una escuela con 1000 alumnos. Quieres saber rápidamente: "¿Cuál es la calificación más alta entre el alumno 50 y el 200?". Además, a veces cambias calificaciones. En vez de revisar uno por uno, organizas a los alumnos en un árbol donde cada nodo guarda información resumida de un rango.

Un Segment Tree es un árbol binario completo donde:

• Cada hoja representa un elemento del arreglo.
• Cada nodo interno guarda el resultado de combinar sus dos hijos (suma, mínimo, máximo, etc.).

Arreglo: [2, 1, 5, 3, 4, 7]

              22          ← suma total
           /      \
         8          14
        / \        / \
       3    5    7    7
      / \   |   / \   |
     2   1  5  3   4   7

Implementación básica (suma)

Usamos un arreglo tree[] de tamaño $4n$. El nodo v tiene hijos 2v y 2v+1.

const int MAXN = 200005;
int tree[4 * MAXN];
int arr[MAXN];
int n;

// Construir el árbol
void build(int v, int tl, int tr) {
    if (tl == tr) {
        tree[v] = arr[tl];  // Hoja
        return;
    }

    int tm = (tl + tr) / 2;
    build(2*v, tl, tm);       // Hijo izquierdo
    build(2*v+1, tm+1, tr);   // Hijo derecho
    tree[v] = tree[2*v] + tree[2*v+1];  // Combinar
}

// Consultar suma en [l, r]
int query(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl) return 0;  // Fuera de rango
    if (l <= tl && tr <= r) return tree[v];  // Completamente dentro

    int tm = (tl + tr) / 2;
    return query(2*v, tl, tm, l, r) +
           query(2*v+1, tm+1, tr, l, r);
}

// Actualizar posición pos con valor val
void update(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) {
        tree[v] = val;
        return;
    }

    int tm = (tl + tr) / 2;
    if (pos <= tm) update(2*v, tl, tm, pos, val);
    else update(2*v+1, tm+1, tr, pos, val);

    tree[v] = tree[2*v] + tree[2*v+1];  // Recalcular
}

Uso

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> arr[i];

    build(1, 1, n);  // Construir desde la raíz

    // Consultar suma [2, 5]
    cout << query(1, 1, n, 2, 5) << endl;

    // Cambiar posición 3 a valor 10
    update(1, 1, n, 3, 10);

    return 0;
}

Tanto consulta como actualización son $O(\log n)$.

Segment Tree de mínimo

Solo cambia la operación de combinación:

void build(int v, int tl, int tr) {
    if (tl == tr) { tree[v] = arr[tl]; return; }
    int tm = (tl + tr) / 2;
    build(2*v, tl, tm);
    build(2*v+1, tm+1, tr);
    tree[v] = min(tree[2*v], tree[2*v+1]);  // min en vez de suma
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl) return INT_MAX;  // Neutro del min
    if (l <= tl && tr <= r) return tree[v];
    int tm = (tl + tr) / 2;
    return min(query(2*v, tl, tm, l, r),
               query(2*v+1, tm+1, tr, l, r));
}

Lazy Propagation

¿Qué pasa si quieres sumar un valor a todo un rango? Sin lazy, tendrías que actualizar cada elemento: $O(n)$. Con lazy, es $O(\log n)$.

Idea: Cuando actualizas un rango completo de un nodo, no bajes a los hijos de inmediato. Guarda la actualización "pendiente" (lazy) y aplícala cuando sea necesario.

long long tree[4 * MAXN];
long long lazy[4 * MAXN];

void push(int v) {
    if (lazy[v] != 0) {
        // Propagar a los hijos
        tree[2*v] += lazy[v];
        lazy[2*v] += lazy[v];
        tree[2*v+1] += lazy[v];
        lazy[2*v+1] += lazy[v];
        lazy[v] = 0;
    }
}

void build(int v, int tl, int tr) {
    lazy[v] = 0;
    if (tl == tr) { tree[v] = arr[tl]; return; }
    int tm = (tl + tr) / 2;
    build(2*v, tl, tm);
    build(2*v+1, tm+1, tr);
    tree[v] = tree[2*v] + tree[2*v+1];
}

// Sumar val a todo el rango [l, r]
void rangeUpdate(int v, int tl, int tr, int l, int r, long long val) {
    if (l > tr || r < tl) return;
    if (l <= tl && tr <= r) {
        tree[v] += val * (tr - tl + 1);
        lazy[v] += val;
        return;
    }
    push(v);
    int tm = (tl + tr) / 2;
    rangeUpdate(2*v, tl, tm, l, r, val);
    rangeUpdate(2*v+1, tm+1, tr, l, r, val);
    tree[v] = tree[2*v] + tree[2*v+1];
}

long long query(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl) return 0;
    if (l <= tl && tr <= r) return tree[v];
    push(v);
    int tm = (tl + tr) / 2;
    return query(2*v, tl, tm, l, r) +
           query(2*v+1, tm+1, tr, l, r);
}

Resumen de complejidades

Ejercicio

Dado un arreglo de N enteros, responde Q operaciones:

• 1 l r: suma de [l, r]
• 2 pos val: cambiar arr[pos] = val

#include <iostream>
using namespace std;

const int MAXN = 200005;
long long tree[4 * MAXN];
int arr[MAXN], n, q;

void build(int v, int tl, int tr) {
    if (tl == tr) { tree[v] = arr[tl]; return; }
    int tm = (tl + tr) / 2;
    build(2*v, tl, tm);
    build(2*v+1, tm+1, tr);
    tree[v] = tree[2*v] + tree[2*v+1];
}

long long query(int v, int tl, int tr, int l, int r) {
    if (l > tr || r < tl) return 0;
    if (l <= tl && tr <= r) return tree[v];
    int tm = (tl + tr) / 2;
    return query(2*v, tl, tm, l, r) + query(2*v+1, tm+1, tr, l, r);
}

void update(int v, int tl, int tr, int pos, int val) {
    if (tl == tr) { tree[v] = val; return; }
    int tm = (tl + tr) / 2;
    if (pos <= tm) update(2*v, tl, tm, pos, val);
    else update(2*v+1, tm+1, tr, pos, val);
    tree[v] = tree[2*v] + tree[2*v+1];
}

int main() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> arr[i];
    build(1, 1, n);

    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int l, r;
            cin >> l >> r;
            cout << query(1, 1, n, l, r) << "\n";
        } else {
            int pos, val;
            cin >> pos >> val;
            update(1, 1, n, pos, val);
        }
    }
    return 0;
}