Árboles de segmentos (IV): Árboles persistentes

En los manuales anteriores, hemos visto como se consultan y modifican los árboles de segmentos. También nos podría interesar hacer consultas en versiones anteriores del árbol, por ejemplo hacer una consulta al árbol tal como estaba antes de las últimas 5 modificaciones. Aquí veremos como mantener todas las versiones que ha habido del árbol, sin utilizar demasiada memoria ni tiempo de cálculo. A estas estructuras se les llama árboles de segmentos persistentes.

Árboles de segmentos con punteros

Los árboles de segmentos se pueden almacenar con vectores o con structs. Para los persistentes, nos será más cómodo hacer-lo con structs. El código de un árbol de segmento con structs es el siguiente:

struct node {
    int a, b;
    node *l, *r;
    int suma;

    node() {}
    node(const vector<int>& v, int left, int right) {
        a = left;
        b = right;
        if(b == a+1) {
            suma = v[a];
            l = r = nullptr;
        } else {
            l = new node(v, left, (left+right)/2);
            r = new node(v, (left+right)/2, right);
            suma = l->suma+r->suma;
        }
    }

    int query(int left, int right) {
        if(right <= a or left >= b)
            return 0;
        if(left <= a and right >= b)
            return suma;
        return l->query(left, right) + r->query(left, right);
    }

    void update(int pos, int v) {
        if(pos == a and a == b-1)
            suma = v;
        else {
            if(pos < (a+b)/2)
                l->update(pos, v);
            else
                r->update(pos, v);
            suma = l->suma + r->suma;
        }
    }
};

Este árbol de segmentos nos permite responder al valor de la suma de un rango, con actualizaciones de un valor. Cada nodo corresponde al segmento $[a, b)$. Su hijo izquierdo, $l$, cubrirá el rango $\left[a, \frac{a+b}{2}\right)$ y el derecho, $r$, cubrirá el rango $\left[\frac{a+b}{2}, b\right)$.

Árboles de segmentos persistentes

Para hacer árboles de segmentos persistentes, cuando nos pidan actualizar el árbol no lo modificaremos, sino que haremos una copia del árbol (que se hará en tiempo constante, gracias al uso de los punteros) y devolveremos esa copia.

Entonces nos guardaremos todas las copias y si nos preguntan por la $k$-ésima, lo podremos hacer fácilmente, ya que la tenemos guardada.

El código del constructor del árbol y de las consultas se quedará igual, pero necesitaremos implementar el método para hacer la copia y modificar el método de modificación, que serán así:

node* copy() {
    node *newNode = new node();
    newNode->a = a;
    newNode->b = b;
    newNode->l = l;
    newNode->r = r;
    newNode->suma = suma;
    return newNode;
}

node* update(int pos, int v) {
    // hacemos la cópia
    node* newNode = copy();
    // si estamos en una hoja cambiamos su valor
    if(pos == a and a == b-1)
        newNode->suma = v;
    else {
        // si no, hacemos la update del hijo correspondiente y lo guardamos como su hijo
        if(pos < (a+b)/2)
            newNode->l = newNode->l->mod(pos, v);
        else
            newNode->r = newNode->r->mod(pos, v);
        newNode->suma = newNode->l->suma + newNode->r->suma;
    }
    return newNode;
}

Para la utilización de esta estructura, tendremos que hacer el código principal de la siguiente forma:

int main(){
    int n; cin >> n;
    vector<int> v(n);
    for(int& x: v)
        cin >> x;

    vector<node*> roots;
    roots.push_back(new node(v, 0, n));
    
    int q; cin >> q;
    while(q--) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        if(a == 1)
            roots.push_back(roots[b]->mod(c, d));
        else
            cout << roots[b]->query(c, d) << endl;
    }
}

En este código, las queries que nos hacen serían de dos tipos, el tipo $a=1$ será que al árbol $b$ modifiquemos la posición $c$ por el valor $d$ y el tipo $a=1$ será que hagamos la consulta del rango $[c,d)$ en el la $b$-ésimo árbol de los que tenemos.