Трюк для DSU (disjoint set union), с которым я недавно столкнулся:

У нас есть элементы, над которыми нужно выполнять два типа запросов:

1. Union — объединить множества, содержащие элементы v1 и v2.
2. Add — для всех i в множестве, содержащем элемент v, прибавить некоторое значение x к a[i].

Чтобы поддерживать это эффективно, можно хранить неявные модификации в вершинах — аналогично ленивым обновлениям (lazy propagation) в дереве отрезков, но без явной передачи изменений вниз.

При запросе Add мы находим корень дерева, содержащего вершину v, и добавляем модификацию в этот корень. Когда нужно получить реальное значение a[i], мы сначала выполняем сжатие пути к корню и применяем модификации от корня. Во время сжатия пути (в процессе рекурсивного переподключения вершин) мы также применяем модификацию родителя к текущей вершине.

Для операции Union можно действовать двумя способами:

1. Создать новую виртуальную вершину, которая станет родителем обоих компонентов.
2. Прикрепить один корень к другому и применить обратную модификацию к поддереву, которое становится потомком.

Второй способ немного сложнее в реализации, особенно если модификации более сложные.

void apply(int v, long long add) {
    res[v] += add;
    lazyAdd[v] += add;
}

int getPar(int v) {
    if (v == comp[v]) return v;
    int p = getPar(comp[v]);
    if (comp[v] != p) apply(v, lazyAdd[comp[v]]);
    return comp[v] = p;
}

long long getVal(int v) {
    int p = getPar(v);
    if (v == p) return res[v];
    return res[v] + lazyAdd[p];
}

void add(int v, long long x) {
    v = getPar(v);
    apply(v, x);
}

void unionSet(int v1, int v2) {
    v1 = getPar(v1);
    v2 = getPar(v2);
    if (v1 == v2) return;

    int p = ++allNodes;
    comp[v1] = p;
    comp[v2] = p;

    res[p] = 0;
    lazyAdd[p] = 0;
    sz[p] = sz[v1] + sz[v2] + 1;
}