Borrar de una estructura de datos en $O(T(n)\log n)$

Supongamos que tenemos una estructura de datos que permite agregar elementos en verdadero $O(T(n))$ . Este artículo describe una técnica que permite borrar en $O(T(n)\log n)$ de forma offline.

Algoritmo

Cada elemento vive en la estructura de datos durante algunos segmentos de tiempo entre altas y bajas. Construyamos un Árbol de Segmentos sobre las consultas. Cada segmento en el que un elemento está vivo se parte en $O(\log n)$ nodos del árbol. Pongamos cada consulta en la que queremos saber algo sobre la estructura en la hoja correspondiente. Ahora, para procesar todas las consultas, recorremos el Árbol de Segmentos con un DFS. Al entrar en un nodo, agregamos todos los elementos que están dentro de ese nodo. Luego avanzamos a los hijos de ese nodo o respondemos las consultas (si el nodo es una hoja). Al salir del nodo, hay que deshacer las altas. Nótese que si modificamos la estructura en $O(T(n))$ podemos revertir los cambios en $O(T(n))$ manteniendo una pila de cambios. Nótese que los rollbacks rompen la complejidad amortizada.

Notas

La idea de crear un Árbol de Segmentos sobre los segmentos en los que algo está vivo no solo sirve para problemas de estructuras de datos. Véanse algunos problemas más abajo.

Implementación

Esta implementación es para el problema de conectividad dinámica . Puede agregar aristas, quitar aristas y contar el número de componentes conexas.


struct dsu_save {
    int v, rnkv, u, rnku;

    dsu_save() {}

    dsu_save(int _v, int _rnkv, int _u, int _rnku)
        : v(_v), rnkv(_rnkv), u(_u), rnku(_rnku) {}
};

struct dsu_with_rollbacks {
    vector<int> p, rnk;
    int comps;
    stack<dsu_save> op;

    dsu_with_rollbacks() {}

    dsu_with_rollbacks(int n) {
        p.resize(n);
        rnk.resize(n);
        for (int i = 0; i < n; i++) {
            p[i] = i;
            rnk[i] = 0;
        }
        comps = n;
    }

    int find_set(int v) {
        return (v == p[v]) ? v : find_set(p[v]);
    }

    bool unite(int v, int u) {
        v = find_set(v);
        u = find_set(u);
        if (v == u)
            return false;
        comps--;
        if (rnk[v] > rnk[u])
            swap(v, u);
        op.push(dsu_save(v, rnk[v], u, rnk[u]));
        p[v] = u;
        if (rnk[u] == rnk[v])
            rnk[u]++;
        return true;
    }

    void rollback() {
        if (op.empty())
            return;
        dsu_save x = op.top();
        op.pop();
        comps++;
        p[x.v] = x.v;
        rnk[x.v] = x.rnkv;
        p[x.u] = x.u;
        rnk[x.u] = x.rnku;
    }
};

struct query {
    int v, u;
    bool united;
    query(int _v, int _u) : v(_v), u(_u) {
    }
};

struct QueryTree {
    vector<vector<query>> t;
    dsu_with_rollbacks dsu;
    int T;

    QueryTree() {}

    QueryTree(int _T, int n) : T(_T) {
        dsu = dsu_with_rollbacks(n);
        t.resize(4 * T + 4);
    }

    void add_to_tree(int v, int l, int r, int ul, int ur, query& q) {
        if (ul > ur)
            return;
        if (l == ul && r == ur) {
            t[v].push_back(q);
            return;
        }
        int mid = (l + r) / 2;
        add_to_tree(2 * v, l, mid, ul, min(ur, mid), q);
        add_to_tree(2 * v + 1, mid + 1, r, max(ul, mid + 1), ur, q);
    }

    void add_query(query q, int l, int r) {
        add_to_tree(1, 0, T - 1, l, r, q);
    }

    void dfs(int v, int l, int r, vector<int>& ans) {
        for (query& q : t[v]) {
            q.united = dsu.unite(q.v, q.u);
        }
        if (l == r)
            ans[l] = dsu.comps;
        else {
            int mid = (l + r) / 2;
            dfs(2 * v, l, mid, ans);
            dfs(2 * v + 1, mid + 1, r, ans);
        }
        for (query q : t[v]) {
            if (q.united)
                dsu.rollback();
        }
    }

    vector<int> solve() {
        vector<int> ans(T);
        dfs(1, 0, T - 1, ans);
        return ans;
    }
};

Borrar de una estructura de datos en O(T(n)log⁡n)O(T(n)\log n)O(T(n)logn)

Algoritmo

Notas

Implementación

Problemas

Borrar de una estructura de datos en $O(T(n)\log n)$