Estructuras Avanzadassegment-treeestructuras-de-datosconsultasrangos

Segment Tree

Domina el Segment Tree para consultas y actualizaciones eficientes en rangos

OOI Oaxaca9 de febrero de 20269 min read

¿Qué es un Segment Tree?

Un Segment Tree es una estructura de datos que permite:

Consultas en rangos en $O(\log n)$
Actualizaciones en $O(\log n)$

Es un árbol binario donde cada nodo representa un segmento (rango) del array.

Array: [1, 3, 5, 7, 9, 11]

                [36]            (0-5) suma total
               /    \
           [9]      [27]        (0-2) (3-5)
          /   \    /    \
        [4]  [5] [16]  [11]     (0-1) (2) (3-4) (5)
        / \      /  \
      [1][3]   [7] [9]          (0) (1) (3) (4)

Operaciones soportadas

Operación	Complejidad
Construir	$O(n)$
Consulta de rango	$O(\log n)$
Actualización puntual	$O(\log n)$
Actualización de rango*	$O(\log n)$

*Con lazy propagation

Implementación básica (Suma)

const int MAXN = 100005;
int arr[MAXN];
int st[4 * MAXN];  // 4n es suficiente espacio

// Construir el árbol
void build(int node, int start, int end) {
    if (start == end) {
        st[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        st[node] = st[2 * node] + st[2 * node + 1];
    }
}

// Consulta de suma en rango [L, R]
int query(int node, int start, int end, int L, int R) {
    if (R < start || end < L) {
        return 0;  // Fuera de rango
    }
    if (L <= start && end <= R) {
        return st[node];  // Completamente dentro
    }

    int mid = (start + end) / 2;
    int izq = query(2 * node, start, mid, L, R);
    int der = query(2 * node + 1, mid + 1, end, L, R);
    return izq + der;
}

// Actualizar posición idx con valor val
void update(int node, int start, int end, int idx, int val) {
    if (start == end) {
        arr[idx] = val;
        st[node] = val;
    } else {
        int mid = (start + end) / 2;
        if (idx <= mid) {
            update(2 * node, start, mid, idx, val);
        } else {
            update(2 * node + 1, mid + 1, end, idx, val);
        }
        st[node] = st[2 * node] + st[2 * node + 1];
    }
}

Uso

int main() {
    int n = 6;
    arr[0] = 1; arr[1] = 3; arr[2] = 5;
    arr[3] = 7; arr[4] = 9; arr[5] = 11;

    build(1, 0, n - 1);

    cout << query(1, 0, n - 1, 1, 3) << endl;  // 3+5+7 = 15

    update(1, 0, n - 1, 2, 10);  // arr[2] = 10

    cout << query(1, 0, n - 1, 1, 3) << endl;  // 3+10+7 = 20

    return 0;
}

Segment Tree para mínimo

int st[4 * MAXN];

void build(int node, int start, int end) {
    if (start == end) {
        st[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        st[node] = min(st[2 * node], st[2 * node + 1]);  // Cambio aquí
    }
}

int query(int node, int start, int end, int L, int R) {
    if (R < start || end < L) return INT_MAX;  // Elemento neutro
    if (L <= start && end <= R) return st[node];

    int mid = (start + end) / 2;
    return min(query(2 * node, start, mid, L, R),
               query(2 * node + 1, mid + 1, end, L, R));
}

Segment Tree para GCD

int st[4 * MAXN];

void build(int node, int start, int end) {
    if (start == end) {
        st[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        st[node] = __gcd(st[2 * node], st[2 * node + 1]);
    }
}

Lazy Propagation

Para actualizaciones de rango eficientes, usamos lazy propagation:

const int MAXN = 100005;
long long st[4 * MAXN];
long long lazy[4 * MAXN];

void push(int node, int start, int end) {
    if (lazy[node] != 0) {
        st[node] += (end - start + 1) * lazy[node];
        if (start != end) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}

void build(int node, int start, int end) {
    lazy[node] = 0;
    if (start == end) {
        st[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        st[node] = st[2 * node] + st[2 * node + 1];
    }
}

// Sumar val a todos los elementos en [L, R]
void updateRange(int node, int start, int end, int L, int R, long long val) {
    push(node, start, end);

    if (R < start || end < L) return;

    if (L <= start && end <= R) {
        lazy[node] += val;
        push(node, start, end);
        return;
    }

    int mid = (start + end) / 2;
    updateRange(2 * node, start, mid, L, R, val);
    updateRange(2 * node + 1, mid + 1, end, L, R, val);
    st[node] = st[2 * node] + st[2 * node + 1];
}

long long query(int node, int start, int end, int L, int R) {
    push(node, start, end);

    if (R < start || end < L) return 0;
    if (L <= start && end <= R) return st[node];

    int mid = (start + end) / 2;
    return query(2 * node, start, mid, L, R) +
           query(2 * node + 1, mid + 1, end, L, R);
}

Segment Tree iterativo

Más rápido y con menos memoria:

const int MAXN = 100005;
int n;
int st[2 * MAXN];

void build() {
    // Los nodos hoja están en posiciones n a 2n-1
    for (int i = 0; i < n; i++) {
        st[n + i] = arr[i];
    }
    // Construir nodos internos
    for (int i = n - 1; i > 0; i--) {
        st[i] = st[2 * i] + st[2 * i + 1];
    }
}

void update(int pos, int val) {
    pos += n;
    st[pos] = val;
    while (pos > 1) {
        pos /= 2;
        st[pos] = st[2 * pos] + st[2 * pos + 1];
    }
}

int query(int L, int R) {
    int resultado = 0;
    L += n;
    R += n + 1;
    while (L < R) {
        if (L & 1) resultado += st[L++];
        if (R & 1) resultado += st[--R];
        L /= 2;
        R /= 2;
    }
    return resultado;
}

Problemas clásicos

1. Contar elementos mayores que X en rango

Usar segment tree con información adicional (merge sort tree):

vector<int> st[4 * MAXN];

void build(int node, int start, int end) {
    if (start == end) {
        st[node] = {arr[start]};
    } else {
        int mid = (start + end) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);

        // Merge ordenado
        merge(st[2*node].begin(), st[2*node].end(),
              st[2*node+1].begin(), st[2*node+1].end(),
              back_inserter(st[node]));
    }
}

int query(int node, int start, int end, int L, int R, int x) {
    if (R < start || end < L) return 0;
    if (L <= start && end <= R) {
        // Contar elementos > x
        return st[node].end() - upper_bound(st[node].begin(), st[node].end(), x);
    }

    int mid = (start + end) / 2;
    return query(2*node, start, mid, L, R, x) +
           query(2*node+1, mid+1, end, L, R, x);
}

2. Máximo prefijo/sufijo

struct Nodo {
    long long suma, prefijo, sufijo, maxSeg;
};

Nodo st[4 * MAXN];

Nodo combinar(Nodo izq, Nodo der) {
    Nodo res;
    res.suma = izq.suma + der.suma;
    res.prefijo = max(izq.prefijo, izq.suma + der.prefijo);
    res.sufijo = max(der.sufijo, der.suma + izq.sufijo);
    res.maxSeg = max({izq.maxSeg, der.maxSeg, izq.sufijo + der.prefijo});
    return res;
}

Template completo

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
int n;
long long arr[MAXN];
long long st[4 * MAXN];
long long lazy[4 * MAXN];

void push(int node, int start, int end) {
    if (lazy[node] != 0) {
        st[node] += (long long)(end - start + 1) * lazy[node];
        if (start != end) {
            lazy[2*node] += lazy[node];
            lazy[2*node+1] += lazy[node];
        }
        lazy[node] = 0;
    }
}

void build(int node, int start, int end) {
    lazy[node] = 0;
    if (start == end) {
        st[node] = arr[start];
    } else {
        int mid = (start + end) / 2;
        build(2*node, start, mid);
        build(2*node+1, mid+1, end);
        st[node] = st[2*node] + st[2*node+1];
    }
}

void update(int node, int start, int end, int L, int R, long long val) {
    push(node, start, end);
    if (R < start || end < L) return;
    if (L <= start && end <= R) {
        lazy[node] += val;
        push(node, start, end);
        return;
    }
    int mid = (start + end) / 2;
    update(2*node, start, mid, L, R, val);
    update(2*node+1, mid+1, end, L, R, val);
    st[node] = st[2*node] + st[2*node+1];
}

long long query(int node, int start, int end, int L, int R) {
    push(node, start, end);
    if (R < start || end < L) return 0;
    if (L <= start && end <= R) return st[node];
    int mid = (start + end) / 2;
    return query(2*node, start, mid, L, R) +
           query(2*node+1, mid+1, end, L, R);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int q;
    cin >> n >> q;

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

    build(1, 0, n - 1);

    while (q--) {
        int tipo;
        cin >> tipo;

        if (tipo == 1) {
            int L, R;
            long long val;
            cin >> L >> R >> val;
            update(1, 0, n-1, L-1, R-1, val);
        } else {
            int L, R;
            cin >> L >> R;
            cout << query(1, 0, n-1, L-1, R-1) << "\n";
        }
    }

    return 0;
}

Resumen

Variante	Uso
Segment Tree básico	Consultas/actualizaciones puntuales
Con Lazy Propagation	Actualizaciones de rango
Iterativo	Más rápido, menos memoria
Merge Sort Tree	Consultas de conteo ordenado