Algoritmo de Classificação Rápida (Quick Sort)

O Quick Sort é um algoritmo de classificação eficiente baseado no paradigma de dividir para conquistar. Ele seleciona um elemento como pivô e particiona o array em dois sub-arrays, um com elementos menores que o pivô e outro com elementos maiores. Em seguida, aplica recursivamente o mesmo processo aos sub-arrays.

void ordenarRapido(int arr[], int inicio, int fim) {
    if (inicio >= fim) return;

    // Escolhe o pivô como o elemento do meio e inicializa os ponteiros
    int ptrEsquerda = inicio - 1, ptrDireita = fim + 1;
    int pivot = arr[inicio + (fim - inicio) / 2]; // Evita overflow para (inicio + fim) grande

    while (ptrEsquerda < ptrDireita) {
        // Encontra um elemento à esquerda maior ou igual ao pivô
        do ptrEsquerda++; while (arr[ptrEsquerda] < pivot);
        // Encontra um elemento à direita menor ou igual ao pivô
        do ptrDireita--; while (arr[ptrDireita] > pivot);

        // Se os ponteiros não se cruzaram, troca os elementos
        if (ptrEsquerda < ptrDireita) {
            std::swap(arr[ptrEsquerda], arr[ptrDireita]);
        }
    }
    // As chamadas recursivas particionam o array em torno do ponteiro da direita.
    // O elemento no índice 'ptrDireita' agora está em sua posição final correta.
    ordenarRapido(arr, inicio, ptrDireita);
    ordenarRapido(arr, ptrDireita + 1, fim);
}

Algoritmo de Classificação por Fusão (Merge Sort)

O Merge Sort também é um algoritmo de dividir para conquistar. Ele divide repetidamente o array em duas metades até que cada metade contenha apenas um elemento (que é considerado classificado). Em seguida, mescla essas metades de forma ordenada até que todo o array esteja classificado.

// É comum usar um array auxiliar global ou passado como parâmetro para a fusão
// int arrayAuxiliar[TAMANHO_MAXIMO]; // Exemplo de declaração global para array auxiliar

void ordenarPorFusao(int arr[], int inicio, int fim) {
    if (inicio >= fim) return;

    int meio = inicio + (fim - inicio) / 2;
    ordenarPorFusao(arr, inicio, meio);         // Classifica a primeira metade
    ordenarPorFusao(arr, meio + 1, fim);     // Classifica a segunda metade

    // Mescla as duas metades classificadas
    // Assumindo que 'arrayAuxiliar' é um array acessível (e.g., global)
    static int arrayAuxiliar[100005]; // Exemplo de declaração estática para fins de demonstração
    int k = 0; // Índice para o array auxiliar
    int idxEsquerda = inicio; // Ponteiro para a primeira metade
    int idxDireita = meio + 1; // Ponteiro para a segunda metade

    // Copia elementos para o array auxiliar em ordem classificada
    while (idxEsquerda <= meio && idxDireita <= fim) {
        if (arr[idxEsquerda] < arr[idxDireita]) {
            arrayAuxiliar[k++] = arr[idxEsquerda++];
        } else {
            arrayAuxiliar[k++] = arr[idxDireita++];
        }
    }

    // Copia os elementos restantes da primeira metade (se houver)
    while (idxEsquerda <= meio) {
        arrayAuxiliar[k++] = arr[idxEsquerda++];
    }
    // Copia os elementos restantes da segunda metade (se houver)
    while (idxDireita <= fim) {
        arrayAuxiliar[k++] = arr[idxDireita++];
    }

    // Copia os elementos classificados do array auxiliar de volta para o array original
    for (int i = inicio, j = 0; i <= fim; i++, j++) {
        arr[i] = arrayAuxiliar[j];
    }
}

Busca Binária para Inteiros

A busca binária é um algoritmo eficiente para encontrar um elemento em um array classificado ou para determinar uma posição que satisfaça uma condição. Existem duas variações comuns, dependendo de como o intervalo é dividido e qual limite é ajustado.

Modelo 1: Busca pelo primeiro elemento que satisfaz a condição (intervalo [baixo, meio] ou [meio + 1, cima])

Este modelo é usado quando a função verifica(meio) é verdadeira para o resultado e todos os valores menores. A busca converge para o menor valor que satisfaz a condição.

// bool verifica(int valor) { /* ... */ } // Função de exemplo para verificar a condição

int buscaBinariaPrimeiro(int baixo, int cima) {
   while (baixo < cima) {
       int meio = baixo + (cima - baixo) / 2; // (baixo + cima) >> 1
       if (verifica(meio)) {
           cima = meio; // 'meio' pode ser o resultado, tenta na metade inferior
       } else {
           baixo = meio + 1; // 'meio' não satisfaz, resultado está na metade superior
       }
   }
   return baixo; // Retorna o primeiro valor que satisfaz a condição
}

Modelo 2: Busca pelo último elemento que satisfaz a condição (intervalo [baixo, meio - 1] ou [meio, cima])

Este modelo é usado quando a função verifica(meio) é verdadeira para o resultado e todos os valores maiores. A busca converge para o maior valor que satisfaz a condição.

int buscaBinariaUltimo(int baixo, int cima) {
    while (baixo < cima) {
        int meio = baixo + (cima - baixo + 1) / 2; // Para evitar loop infinito quando baixo = meio
        if (verifica(meio)) {
            baixo = meio; // 'meio' pode ser o resultado, tenta na metade superior
        } else {
            cima = meio - 1; // 'meio' não satisfaz, resultado está na metade inferior
        }
    }
    return baixo; // Retorna o último valor que satisfaz a condição
}

Busca Binária para Ponto Flutuante

A busca binária para números de ponto flutuante é similar à inteira, mas em vez de contar iterações, ela converge até que a diferença entre os limites superior e inferior esteja dentro de uma precisão aceitável (epsilon).

// bool verifica(double valor) { /* ... */ } // Função de exemplo para verificar a condição

double buscaBinariaPontoFlutuante(double limiteInferior, double limiteSuperior) {
    const double precisao = 1e-7; // Ajuste 'precisao' conforme a necessidade do problema
    while (limiteSuperior - limiteInferior > precisao) {
        double meio = (limiteInferior + limiteSuperior) / 2;
        if (verifica(meio)) {
            limiteSuperior = meio; // 'meio' pode ser o resultado, busca na metade inferior
        } else {
            limiteInferior = meio; // 'meio' não satisfaz, busca na metade superior
        }
    }
    return limiteInferior; // Retorna o valor aproximado
}

Aritmética de Alta Precisão: Soma

Para somar números inteiros muito grandes que excedem os limites dos tipos de dados padrão (como long long), podemos representá-los como vetores de dígitos (geralmente armazenados na ordem inversa para facilitar as operações).

Pré-condição: resultado = num1 + num2, onde num1 >= 0 e num2 >= 0.

std::vector<int> somaGrandesNumeros(std::vector<int> &num1, std::vector<int> &num2) {
    // Garante que num1 seja o número com mais dígitos ou de tamanho igual
    if (num1.size() < num2.size()) {
        return somaGrandesNumeros(num2, num1);
    }

    std::vector<int> resultado;
    int carry = 0; // Armazena o "vai um" (carry)

    for (int i = 0; i < num1.size(); i++) {
        carry += num1[i]; // Adiciona o dígito de num1
        if (i < num2.size()) {
            carry += num2[i]; // Adiciona o dígito de num2, se existir
        }
        resultado.push_back(carry % 10); // Adiciona o dígito da soma
        carry /= 10; // Atualiza o carry
    }

    if (carry) { // Se ainda houver um carry no final
        resultado.push_back(carry);
    }
    return resultado;
}

Aritmética de Alta Precisão: Subtração

A subtração de números grandes é implementada de forma similar à adição, mas lidando com "empréstimos" (borrows) entre os dígitos.

Pré-condição: diferenca = minuendo - subtraendo, onde minuendo >= subtraendo, minuendo >= 0 e subtraendo >= 0.

std::vector<int> subtraiGrandesNumeros(std::vector<int> &minuendo, std::vector<int> &subtraendo) {
    std::vector<int> diferenca;
    int emprestimo = 0; // Armazena o "pega emprestado" (borrow)

    for (int i = 0; i < minuendo.size(); i++) {
        int digitoAtual = minuendo[i] - emprestimo; // Subtrai o empréstimo anterior
        if (i < subtraendo.size()) {
            digitoAtual -= subtraendo[i]; // Subtrai o dígito do subtraendo, se existir
        }

        diferenca.push_back((digitoAtual + 10) % 10); // Adiciona o dígito resultante (garante positivo)

        if (digitoAtual < 0) { // Se o resultado temporário for negativo, houve um empréstimo
            emprestimo = 1;
        } else {
            emprestimo = 0;
        }
    }

    // Remove zeros à esquerda (exceto se o resultado for apenas '0')
    while (diferenca.size() > 1 && diferenca.back() == 0) {
        diferenca.pop_back();
    }
    return diferenca;
}

Aritmética de Alta Precisão: Multiplicação por Inteiro Único

A multiplicação de um número grande por um inteiro de baixa precisão é realizada dígito a dígito, similar à multiplicação manual.

Pré-condição: produto = fatorGrande * fatorPequeno, onde fatorGrande >= 0 e fatorPequeno > 0.

std::vector<int> multiplicaGrandePorInt(std::vector<int> &fatorGrande, int fatorPequeno) {
    std::vector<int> produto;
    if (fatorPequeno == 0) return {0}; // Caso especial: multiplicação por zero

    int carry = 0; // Armazena o "vai um"

    for (int i = 0; i < fatorGrande.size() || carry; i++) {
        if (i < fatorGrande.size()) {
            carry += fatorGrande[i] * fatorPequeno; // Multiplica dígito por fatorPequeno e adiciona carry
        }
        produto.push_back(carry % 10); // Adiciona o dígito resultante
        carry /= 10; // Atualiza o carry
    }

    // Remove zeros à esquerda, se houver
    while (produto.size() > 1 && produto.back() == 0) {
        produto.pop_back();
    }
    return produto;
}

Aritmética de Alta Precisão: Divisão por Inteiro Único

A divisão de um número grande por um inteiro de baixa precisão simula o processo de "divisão longa" que aprendemos na escola.

Pré-condição: dividendo / divisor = quociente ... resto, onde dividendo >= 0 e divisor > 0.

std::vector<int> divideGrandePorInt(std::vector<int> &dividendo, int divisor, int &resto) {
    std::vector<int> quociente;
    resto = 0; // Inicializa o resto

    // Itera os dígitos do dividendo da esquerda para a direita (do mais significativo ao menos significativo)
    for (int i = dividendo.size() - 1; i >= 0; i--) {
        resto = resto * 10 + dividendo[i]; // Incorpora o próximo dígito ao resto atual
        quociente.push_back(resto / divisor); // Calcula o dígito do quociente
        resto %= divisor; // Atualiza o resto
    }

    std::reverse(quociente.begin(), quociente.end()); // Os dígitos foram adicionados em ordem inversa, agora os inverte

    // Remove zeros à esquerda (exceto se o quociente for apenas '0')
    while (quociente.size() > 1 && quociente.back() == 0) {
        quociente.pop_back();
    }
    return quociente;
}

Soma de Prefixos (Prefix Sum) em Uma Dimensão

A soma de prefixos é uma técnica para calcular eficientemente a soma de elementos em sub-arrays. Um array de soma de prefixos S armazena a soma cumulativa dos elementos de um array original A.

• S[i] = A[0] + A[1] + ... + A[i] (considerando indexação base 0)
• A soma dos elementos de A[inicio] a A[fim] (enclusive) é S[fim] - S[inicio - 1]. Se inicio = 0, a soma é S[fim].

Soma de Prefixos (Prefix Sum) em Duas Dimensões

Similarmente, para matrrizes, uma matriz de soma de prefixos S armazena a soma de todos os elementos em uma sub-matriz que vai de (0,0) até (i,j).

• S[i, j] representa a soma de todos os elementos na região retangular superior-esquerda até a célula (i, j).
• A soma de uma sub-matriz com canto superior-esquerdo (x1, y1) e canto inferior-direito (x2, y2) é calculada por:
  S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1] (onde S[qualquer_indice_negativo] é considerado 0).

Array de Diferenças (Difference Array) em Uma Dimansão

O array de diferenças D é usado para realizar eficientes atualizações de intervalo em um array A. Para adicionar um valor c a todos os elementos no intervalo [l, r] (inclusive), podemos atualizar apenas dois pontos no array de diferenças:

• D[l] += c
• D[r + 1] -= c

Após todas as atualizações, o array original A pode ser reconstruído a partir de D usando uma soma de prefixos em D.

Array de Diferenças (Difference Array) em Duas Dimensões

Para aplicar um valor c a todos os elementos de uma sub-matriz com canto superior-esquerdo (x1, y1) e canto inferior-direito (x2, y2):

• D[x1, y1] += c
• D[x2 + 1, y1] -= c
• D[x1, y2 + 1] -= c
• D[x2 + 1, y2 + 1] += c

A matriz original pode ser reconstruída aplicando a soma de prefixos bidimensional ao array de diferenças D.

Operações Bit a Bit

Operações de bit são fundamentais para manipular bits individuais dentro de um número inteiro.

• Para encontrar o k-ésimo bit de um número n (contando do bit 0 à direita): (n >> k) & 1
• Para obter o valor do bit menos significativo (o último '1') de um número n: lowbit(n) = n & (-n). Esta operação é útil em estruturas de dados como Fenwick Trees (BIT).

Algoritmo de Dois Ponteiros

O algoritmo de dois ponteiros é uma técnica comum para resolver problemas que envolvem arrays ou listas, onde dois ponteiros iteram sobre a estrutura, geralmente mantendo alguma propriedade do intervalo entre eles ou comparando elementos.

void exemploDoisPonteiros(int arr[], int n) {
    for (int ptrDireita = 0, ptrEsquerda = 0; ptrDireita < n; ptrDireita++) {
        // Aumenta ptrEsquerda enquanto a condição é satisfeita (ou não)
        // Por exemplo, para manter uma propriedade no intervalo [ptrEsquerda, ptrDireita]
        while (ptrEsquerda < ptrDireita && !condicaoValida(arr, ptrEsquerda, ptrDireita)) {
            ptrEsquerda++;
        }

        // Lógica específica do problema com o intervalo [ptrEsquerda, ptrDireita]
        // Ex: calcular soma, comprimento máximo, etc.
    }
}

Categorias comuns de problemas:

1. Manter um intervalo ou janela em um único array ou sequência.
2. Mesclar ou encontrar relações entre dois arrays ordenados (ex: fase de mesclagem do Merge Sort).

Discretização

A discretização é uma técnica para mapear valores de um grande domínio (por exemplo, coordenadas muito grandes) para um domínio menor e contíguo (como índices 0, 1, 2, ...). Isso é útil quando apenas a ordem relativa dos valores importa, e não seus valores absolutos.

std::vector<int> discretizar(const std::vector<int> &data) {
    std::vector<int> valoresUnicos = data; // Copia os dados para processamento
    std::sort(valoresUnicos.begin(), valoresUnicos.end()); // Ordena todos os valores
    // Remove elementos duplicados, mantendo apenas valores únicos
    valoresUnicos.erase(std::unique(valoresUnicos.begin(), valoresUnicos.end()), valoresUnicos.end());
    return valoresUnicos;
}

// Função para encontrar o índice discretizado de um valor
// Retorna o índice baseado em 0 (ou 1, se necessário, ajustando o retorno)
int encontrarIndiceDiscretizado(int valor, const std::vector<int> &valoresUnicos) {
    // std::lower_bound retorna um iterador para o primeiro elemento >= valor
    auto it = std::lower_bound(valoresUnicos.begin(), valoresUnicos.end(), valor);
    return std::distance(valoresUnicos.begin(), it); // Retorna o índice baseado em 0
}

Mesclagem de Intervalos

A mesclagem de intervalos é um problema comum em que uma lista de intervalos sobrepostos ou adjacentes é combinada em um conjunto mínimo de intervalos não sobrepostos.

#include <vector>
#include <algorithm> // Para std::sort, std::max
#include <utility>   // Para std::pair

// Define um par de inteiros para representar um intervalo [inicio, fim]
using Intervalo = std::pair<int, int>;

std::vector<Intervalo> mesclarIntervalos(std::vector<Intervalo> &intervalos) {
    std::vector<Intervalo> intervalosMesclados;

    if (intervalos.empty()) {
        return intervalosMesclados;
    }

    // Primeiro, ordena os intervalos pelo seu ponto de início
    std::sort(intervalos.begin(), intervalos.end());

    // Inicializa o intervalo atual com o primeiro intervalo da lista ordenada
    int inicioAtual = intervalos[0].first;
    int fimAtual = intervalos[0].second;

    for (size_t i = 1; i < intervalos.size(); ++i) {
        Intervalo proximoIntervalo = intervalos[i];

        // Se o próximo intervalo se sobrepõe ou é adjacente ao intervalo atual
        if (proximoIntervalo.first <= fimAtual) {
            // Estende o fim do intervalo atual
            fimAtual = std::max(fimAtual, proximoIntervalo.second);
        } else {
            // Não há sobreposição, adiciona o intervalo atual aos mesclados
            intervalosMesclados.push_back({inicioAtual, fimAtual});
            // Começa um novo intervalo
            inicioAtual = proximoIntervalo.first;
            fimAtual = proximoIntervalo.second;
        }
    }

    // Adiciona o último intervalo que estava sendo processado
    intervalosMesclados.push_back({inicioAtual, fimAtual});

    return intervalosMesclados;
}