Union-Find (Conjuntos Disjuntos)

Enicialização

A inicialização correta é absolutamente crucial!

// O array 'parent' armazena o pai de cada nó
int parent[N];
for (int idx = 1; idx <= total; idx++) {
    parent[idx] = idx; // Cada nó é seu próprio pai inicialmente
}

Compressão de Caminho

int findRoot(int x) {
    if (parent[x] == x) return x;
    // Compressão de caminho: conecta o nó diretamente à raiz
    return parent[x] = findRoot(parent[x]);
}

void unite(int x, int y) {
    int rootX = findRoot(x);
    int rootY = findRoot(y);
    // Une as árvores se estiverem em componentes diferentes
    if (rootX != rootY) {
        parent[rootY] = rootX;
    }
}

União por Tamanho (Merge Heurístico)

int treeSize[N]; // Armazena o tamanho de cada árvore

// Inicialização
for (int idx = 1; idx <= total; idx++) {
    parent[idx] = idx;
    treeSize[idx] = 1;
}

int findRoot(int x) {
    if (parent[x] == x) return x;
    return findRoot(parent[x]); // Sem compressão de caminho
}

void unite(int x, int y) {
    int rootX = findRoot(x);
    int rootY = findRoot(y);
    if (rootX == rootY) return;
    
    // Anexa a árvore menor sob a maior
    if (treeSize[rootX] < treeSize[rootY]) {
        swap(rootX, rootY);
    }
    parent[rootY] = rootX;
    treeSize[rootX] += treeSize[rootY];
}

Segment Tree (Árvore de Segmentos)

Implementação Básica

Erros Comuns

1. Durante a operação Pushdown, a soma do filho deve adicionar a etiqueta preguiçosa (lazy tag) do nó pai, não a etiqueat preguiçosa do próprio filho.
2. Os limites l e r nas funções Query e Modify permanecem constantes e são propagados para baixo na árvore.

Código de Exemplo

#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
const int MAXN = 1e5 + 5;

struct SegmentNode {
    int left, right;
    ll sum;
    ll pendingUpdate;
};

SegmentNode segTree[4 * MAXN];
ll inputArray[MAXN];
int numElements, numQueries;

void propagate(int nodeIndex) {
    auto& currentNode = segTree[nodeIndex];
    if (currentNode.pendingUpdate != 0) {
        int leftChild = nodeIndex * 2;
        int rightChild = nodeIndex * 2 + 1;
        
        // Propaga para os filhos
        segTree[leftChild].pendingUpdate += currentNode.pendingUpdate;
        segTree[rightChild].pendingUpdate += currentNode.pendingUpdate;
        
        // Atualiza as somas dos filhos
        int leftSize = segTree[leftChild].right - segTree[leftChild].left + 1;
        int rightSize = segTree[rightChild].right - segTree[rightChild].left + 1;
        segTree[leftChild].sum += leftSize * currentNode.pendingUpdate;
        segTree[rightChild].sum += rightSize * currentNode.pendingUpdate;
        
        currentNode.pendingUpdate = 0;
    }
}

void pullUp(int nodeIndex) {
    segTree[nodeIndex].sum = segTree[nodeIndex * 2].sum + segTree[nodeIndex * 2 + 1].sum;
}

void build(int nodeIndex, int l, int r) {
    segTree[nodeIndex].left = l;
    segTree[nodeIndex].right = r;
    segTree[nodeIndex].pendingUpdate = 0;
    
    if (l == r) {
        segTree[nodeIndex].sum = inputArray[l];
        return;
    }
    
    int mid = (l + r) / 2;
    build(nodeIndex * 2, l, mid);
    build(nodeIndex * 2 + 1, mid + 1, r);
    pullUp(nodeIndex);
}

ll querySum(int nodeIndex, int ql, int qr) {
    auto& node = segTree[nodeIndex];
    if (ql <= node.left && node.right <= qr) {
        return node.sum;
    }
    
    propagate(nodeIndex);
    int mid = (node.left + node.right) / 2;
    ll result = 0;
    
    if (ql <= mid) result += querySum(nodeIndex * 2, ql, qr);
    if (qr > mid) result += querySum(nodeIndex * 2 + 1, ql, qr);
    return result;
}

void rangeUpdate(int nodeIndex, int ul, int ur, ll value) {
    auto& node = segTree[nodeIndex];
    if (ul <= node.left && node.right <= ur) {
        node.pendingUpdate += value;
        node.sum += value * (node.right - node.left + 1);
        return;
    }
    
    propagate(nodeIndex);
    int mid = (node.left + node.right) / 2;
    
    if (ul <= mid) rangeUpdate(nodeIndex * 2, ul, ur, value);
    if (ur > mid) rangeUpdate(nodeIndex * 2 + 1, ul, ur, value);
    pullUp(nodeIndex);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> numElements >> numQueries;
    for (int i = 1; i <= numElements; i++) {
        cin >> inputArray[i];
    }
    
    build(1, 1, numElements);
    
    while (numQueries--) {
        int operation;
        cin >> operation;
        
        if (operation == 1) {
            int left, right, increment;
            cin >> left >> right >> increment;
            rangeUpdate(1, left, right, increment);
        } else {
            int left, right;
            cin >> left >> right;
            cout << querySum(1, left, right) << '\n';
        }
    }
    
    return 0;
}