Implementações Comuns de Interfaces
A seguir, exploraremos a reimplementação de algumas funções de interface padrão e componentes de classes, focando em suas lógicas subjacentes e desafios, como tratamento de overflow e gerenciamento de memória.
Função converterStringParaInteiro (Equivalente a atoi)
Esta função converte uma string em um inteiro de 32 bits assinado. Os passos principais para esta conversão incluem:
- Processar a string para remover quaisquer espaços em branco iniciais.
- Verificar o próximo caractere para determinar o sinal (positivo ou negativo) do número. Se nenhum sinal for encontrado, assume-se positivo.
- Ler os caracteres subsequentes, coletando dígitos até encontrar um caractere não numérico ou o fim da string. Quaisquer caracteres após os dígitos são ignorados.
- Converter os dígitos coletados em um valor inteiro, aplicando o sinal determinado. Se nenhum dígito for encontrado, o valor resultante é
0. - Garantir que o valor inteiro resultante esteja dentro do intervalo de um inteiro assinado de 32 bits (
[−2^31, 2^31 − 1]). Valores que excedem esses limites devem ser truncados paraINT_MAXouINT_MIN, conforme apropriado.
#include <string>
#include <climits> // Para INT_MAX e INT_MIN
#include <cctype> // Para isspace e isdigit
// Converte uma string para um inteiro de 32 bits assinado, com tratamento de overflow.
int converterStringParaInteiro(const std::string& strInput) {
long long resultadoNumerico = 0; // Usar long long para verificar overflow antes de atribuir ao int
int sinal = 1; // Assume-se positivo inicialmente
int idx = 0;
int tamanho = strInput.length();
// 1. Ignorar espaços em branco iniciais
while (idx < tamanho && std::isspace(strInput[idx])) {
++idx;
}
// 2. Determinar o sinal (se presente)
if (idx < tamanho) {
if (strInput[idx] == '-') {
sinal = -1;
++idx;
} else if (strInput[idx] == '+') {
++idx;
}
}
// 3. Processar dígitos numéricos
while (idx < tamanho && std::isdigit(strInput[idx])) {
int digito = strInput[idx] - '0';
// 4. Verificar e manipular overflow antes de adicionar o dígito.
// As comparações são feitas com INT_MAX e INT_MIN para garantir que o resultado
// não exceda os limites de um int de 32 bits.
if (sinal == 1) { // Lidar com números positivos
if (resultadoNumerico > INT_MAX / 10 || (resultadoNumerico == INT_MAX / 10 && digito > INT_MAX % 10)) {
return INT_MAX;
}
} else { // Lidar com números negativos
// Para negativos, as comparações são ligeiramente diferentes.
// INT_MIN é -2147483648. INT_MIN % 10 é -8.
// Precisamos garantir que resultadoNumerico (que está sendo construído como negativo)
// não se torne menor que INT_MIN.
if (resultadoNumerico < INT_MIN / 10 || (resultadoNumerico == INT_MIN / 10 && -digito < INT_MIN % 10)) {
return INT_MIN;
}
}
resultadoNumerico = resultadoNumerico * 10 + sinal * digito;
++idx;
}
return static_cast<int>(resultadoNumerico);
}
Função converterInteiroParaString (Equivalente a to_string)
Esta função converte um número inteiro para sua representação em string. O processo envolve extrair dígitos usando a operação de módulo e reconstruir a string, cnosiderando o sinal do número.
#include <string>
#include <algorithm> // Para std::reverse
#include <climits> // Para INT_MIN (caso especial)
// Converte um inteiro para sua representação em string.
std::string converterInteiroParaString(int numero) {
if (numero == 0) return "0";
std::string stringResultante = "";
bool ehNegativo = (numero < 0);
// Tratamento especial para INT_MIN, pois -INT_MIN causa overflow em um int.
// Convertemos o último dígito separadamente e ajustamos o número.
if (numero == INT_MIN) {
stringResultante += '8'; // Último dígito de -2147483648
numero /= 10; // Agora numero é -214748364
numero *= -1; // Torna-o positivo para o loop
} else if (ehNegativo) {
numero *= -1; // Converte para positivo para processamento
}
while (numero > 0) {
char caractereDigito = (numero % 10) + '0'; // Converte dígito para caractere
stringResultante += caractereDigito;
numero /= 10;
}
if (ehNegativo) {
stringResultante += '-';
}
std::reverse(stringResultante.begin(), stringResultante.end()); // Inverte a string para ordem correta
return stringResultante;
}
Implementação de Construtores Especiais em C++
Ao criar classes em C++ que gerenciam recursos (como memória dinâmica), é fundamental implementar corretamente os construtores de cópia e movimento, além do operador de atribuição de cópia e movimento, para garantir a correta semântica de valor e evitar vazamentos de memória ou acessos inválidos.
#include <utility> // Para std::move
class ClasseExemplo {
private:
int* _ponteiroDados; // Ponteiro para um dado inteiro dinamicamente alocado
public:
// Construtor padrão
ClasseExemplo() : _ponteiroDados(nullptr) {}
// Construtor que recebe um ponteiro para um int e aloca uma cópia profunda.
explicit ClasseExemplo(int* ptr) : _ponteiroDados(nullptr) {
if (ptr) {
_ponteiroDados = new int(*ptr);
}
}
// Construtor de cópia (Deep Copy): Cria uma nova cópia do recurso.
ClasseExemplo(const ClasseExemplo& origem) : _ponteiroDados(nullptr) {
if (origem._ponteiroDados) {
_ponteiroDados = new int(*origem._ponteiroDados);
}
}
// Construtor de movimento: Transfere a posse do recurso da origem para o novo objeto.
ClasseExemplo(ClasseExemplo&& origem) noexcept : _ponteiroDados(origem._ponteiroDados) {
origem._ponteiroDados = nullptr; // A origem agora não possui o recurso
}
// Destrutor: Libera o recurso alocado dinamicamente.
~ClasseExemplo() {
if (_ponteiroDados) {
delete _ponteiroDados;
_ponteiroDados = nullptr;
}
}
// Operador de atribuição de cópia: Libera o recurso antigo e aloca uma nova cópia.
ClasseExemplo& operator=(const ClasseExemplo& origem) {
if (this == &origem) { // Verifica autoatribuição
return *this;
}
if (_ponteiroDados) {
delete _ponteiroDados; // Libera o recurso atual
}
if (origem._ponteiroDados) {
_ponteiroDados = new int(*origem._ponteiroDados); // Aloca e copia
} else {
_ponteiroDados = nullptr;
}
return *this;
}
// Operador de atribuição de movimento: Libera o recurso antigo e "rouba" o recurso da origem.
ClasseExemplo& operator=(ClasseExemplo&& origem) noexcept {
if (this == &origem) { // Verifica autoatribuição
return *this;
}
if (_ponteiroDados) {
delete _ponteiroDados; // Libera o recurso atual
}
_ponteiroDados = origem._ponteiroDados; // Transfere o ponteiro
origem._ponteiroDados = nullptr; // Nula o ponteiro da origem
return *this;
}
};
Função copiarString (Equivalente a strcpy)
Copia uma string terminada em nulo de um local de memória de origem para um destino. É crucial garantir que o buffer de destino seja grande o suficiente para acomodar a string de origem, incluindo o caractere nulo terminador, para evitar estouro de buffer.
#include <cstddef> // Para NULL
// Copia a string terminada em nulo de 'origem' para 'destino'.
// Retorna um ponteiro para o início da string de destino.
char* copiarString(char* destino, const char* origem) {
if (destino == NULL || origem == NULL) {
return NULL; // Retorna NULL para ponteiros de entrada inválidos.
}
char* ponteiroInicioDestino = destino; // Salva o ponteiro inicial do destino
// Copia cada caractere da origem para o destino até encontrar o terminador nulo.
while (*origem != '\0') {
*destino = *origem;
destino++;
origem++;
}
*destino = '\0'; // Adiciona o terminador nulo ao final da string copiada.
return ponteiroInicioDestino;
}
Função obterComprimentoString (Equivalente a strlen)
Calcula o comprimento de uma string C-style, contando o número de caracteres até o primeiro caractere nulo ('\0'). O caractere nulo em si não é incluído na contagem.
#include <cstddef> // Para NULL
// Calcula o comprimento da string fornecida, excluindo o terminador nulo.
// Retorna -1 se o ponteiro de entrada for NULL.
int obterComprimentoString(const char* strParaContar) {
if (strParaContar == NULL) {
return -1; // Retorna -1 para indicar um erro (ponteiro nulo).
}
int comprimento = 0;
while ((*strParaContar) != '\0') {
comprimento++;
strParaContar++;
}
return comprimento;
}
Função concatenarStrings (Equivalente a strcat)
Adiciona (concatena) o conteúdo de uma string de origem ao final de uma string de destino. A string de destino deve ter espaço suficiente para a string original mais a string a ser concatenada e o terminador nulo.
#include <cstddef> // Para NULL
// Adiciona a string 'origem' ao final da string 'destino'.
// Retorna um ponteiro para o início da string de destino modificada.
char* concatenarStrings(char* destino, const char* origem) {
if (destino == NULL || origem == NULL) {
return NULL; // Retorna NULL para ponteiros de entrada inválidos.
}
char* ponteiroRetorno = destino; // Salva o ponteiro inicial do destino.
// Move o ponteiro 'destino' até o final da string atual (onde está o '\0').
while ((*destino) != '\0') {
destino++;
}
// Copia os caracteres da 'origem' para o final de 'destino'.
while ((*origem) != '\0') {
*destino = *origem;
destino++;
origem++;
}
*destino = '\0'; // Adiciona o terminador nulo ao final da string concatenada.
return ponteiroRetorno;
}
Função compararStrings (Equivalente a strcmp)
Compara duas strings lexicograficamente. A comparação é baseada nos valores ASCII dos caracteres. Retorna 0 se as strings são iguais, um valor positivo se a primeira string for "maior" e um valor negativo se a primeira string for "menor".
#include <cstddef> // Para NULL
// Compara lexicograficamente duas strings C-style.
// Retorna 0 se as strings forem iguais.
// Retorna >0 se stringA for maior que stringB.
// Retorna <0 se stringA for menor que stringB.
int compararStrings(const char* stringA, const char* stringB) {
// Definimos um comportamento para ponteiros nulos, embora a função padrão
// strcmp tenha comportamento indefinido para tais entradas.
if (stringA == NULL && stringB == NULL) return 0;
if (stringA == NULL) return -1; // Considera NULL como "menor"
if (stringB == NULL) return 1; // Considera NULL como "menor", então stringA é "maior"
// Itera sobre os caracteres até encontrar uma diferença ou o terminador nulo.
while ((*stringA) != '\0' && (*stringB) != '\0' && (*stringA) == (*stringB)) {
stringA++;
stringB++;
}
// Retorna a diferença dos códigos ASCII dos primeiros caracteres diferentes
// ou a diferença dos terminadores nulos se uma string for prefixo da outra.
return static_cast<int>(*stringA) - static_cast<int>(*stringB);
}
Função copiarMemoria (Equivalente a memcpy)
Copia um número especificado de bytes de uma área de memória de origem para uma área de memória de destino. Esta implementação inclui um tratamento para casos de sobreposição de memória, onde std::memmove seria a função padrão mais adequada em C/C++.
#include <cstddef> // Para NULL
// Copia 'numBytes' bytes de 'areaOrigem' para 'areaDestino'.
// Esta implementação tenta lidar com sobreposição de memória, mas 'std::memmove' é o padrão para isso.
char* copiarMemoria(char* areaDestino, const char* areaOrigem, int numBytes) {
if (areaDestino == NULL || areaOrigem == NULL || numBytes <= 0) {
return areaDestino; // Retorna o destino para entradas inválidas ou zero bytes.
}
// Lida com sobreposição de memória: Se a área de destino se sobrepõe
// com a área de origem e começa depois dela, a cópia deve ser feita
// de trás para frente para evitar sobrescrever dados da origem antes que sejam lidos.
if (areaDestino >= areaOrigem && areaDestino < (areaOrigem + numBytes)) {
for (int i = numBytes - 1; i >= 0; --i) {
areaDestino[i] = areaOrigem[i];
}
} else {
// Sem sobreposição ou sobreposição onde a origem começa depois do destino:
// Cópia normal de frente para trás.
for (int i = 0; i < numBytes; ++i) {
areaDestino[i] = areaOrigem[i];
}
}
return areaDestino;
}
Implementando uma Classe MinhaString Customizada
Uma implementação básica de uma classe de string que gerencia sua própria memória, demonstrando o "Rule of Five" (construtor padrão, construtor de cópia, operador de atribuição de cópia, construtor de movimento e operador de atribuição de movimento), além do destrutor.
#include <cstring> // Para std::strlen, std::strcpy
#include <cstddef> // Para size_t
#include <utility> // Para std::move
class MinhaString {
private:
char* _bufferCaracteres; // Ponteiro para o array de caracteres C-style (terminado em nulo)
size_t _tamanho; // Comprimento da string (excluindo o terminador nulo)
public:
// Construtor padrão: Inicializa uma string vazia.
MinhaString() : _bufferCaracteres(nullptr), _tamanho(0) {}
// Construtor com parâmetro C-string: Inicializa a string a partir de um C-string.
// Lida com nullptr para c_str_val.
explicit MinhaString(const char* c_str_val) {
if (c_str_val == nullptr) {
_bufferCaracteres = nullptr;
_tamanho = 0;
} else {
_tamanho = std::strlen(c_str_val);
_bufferCaracteres = new char[_tamanho + 1]; // +1 para o terminador nulo
std::strcpy(_bufferCaracteres, c_str_val);
}
}
// Construtor de cópia: Realiza uma cópia profunda (deep copy) dos dados da string.
MinhaString(const MinhaString& outra) {
_tamanho = outra._tamanho;
_bufferCaracteres = new char[_tamanho + 1];
std::strcpy(_bufferCaracteres, outra._bufferCaracteres);
}
// Construtor de movimento: Transfere a propriedade dos recursos de uma string temporária.
MinhaString(MinhaString&& outra) noexcept
: _bufferCaracteres(outra._bufferCaracteres), _tamanho(outra._tamanho) {
outra._bufferCaracteres = nullptr; // Garante que a origem não tente liberar a memória
outra._tamanho = 0;
}
// Destrutor: Libera a memória alocada dinamicamente.
~MinhaString() {
if (_bufferCaracteres) {
delete[] _bufferCaracteres;
_bufferCaracteres = nullptr;
}
}
// Operador de atribuição de cópia: Permite atribuir uma string a outra, realizando deep copy.
MinhaString& operator=(const MinhaString& outra) {
if (this == &outra) { // Previne autoatribuição
return *this;
}
if (_bufferCaracteres) {
delete[] _bufferCaracteres; // Libera recursos antigos
}
_tamanho = outra._tamanho;
_bufferCaracteres = new char[_tamanho + 1];
std::strcpy(_bufferCaracteres, outra._bufferCaracteres);
return *this;
}
// Operador de atribuição de movimento: Permite atribuir uma string temporária, movendo os recursos.
MinhaString& operator=(MinhaString&& outra) noexcept {
if (this == &outra) { // Previne autoatribuição
return *this;
}
if (_bufferCaracteres) {
delete[] _bufferCaracteres; // Libera recursos antigos
}
_bufferCaracteres = outra._bufferCaracteres; // "Rouba" o ponteiro da origem
_tamanho = outra._tamanho;
outra._bufferCaracteres = nullptr; // Zera a origem
outra._tamanho = 0;
return *this;
}
// Método para obter o comprimento da string.
inline size_t obterComprimento() const {
return _tamanho;
}
// Método para obter o C-string subjacente.
inline const char* c_str() const {
// Retorna um ponteiro para uma string vazia se _bufferCaracteres for nullptr.
return _bufferCaracteres ? _bufferCaracteres : "";
}
};
Outros Conceitos e Estruturas de Dados
Array de Somas de Prefixo (1D)
Um array de somas de prefixo é uma estrutura de dados que permite calcular a soma de qualquer subsegmento de um array original em tempo constante (O(1)), após uma pré-computação inicial de tempo linear (O(N)).
Dada uma sequência A = [a₀, a₁, ..., aₙ₋₁], seu array de somas de prefixo P é definido como:
P[0] = 0P[i] = P[i-1] + A[i-1]parai > 0ei ≤ n
A soma de um intervalo A[l, r] (elementos de índice l a r, inclusive) é calculada como P[r+1] - P[l].
#include <vector>
// Demonstra a construção de um array de somas de prefixos 1D.
void demonstrarSomaPrefixos1D() {
std::vector<int> arrayOriginal = {1, 2, 3, 4, 5};
int tamanhoArray = arrayOriginal.size();
// O array de somas de prefixos terá tamanho N+1, onde P[0] = 0.
std::vector<int> arraySomaPrefixos(tamanhoArray + 1, 0);
// Construção do array de somas de prefixos:
// P[i] armazena a soma de A[0]...A[i-1]
for (int i = 1; i <= tamanhoArray; ++i) {
arraySomaPrefixos[i] = arraySomaPrefixos[i - 1] + arrayOriginal[i - 1];
}
// Exemplo de uso: Calcular a soma do intervalo arrayOriginal[1] a arrayOriginal[3] (índices 1, 2, 3).
// Elementos: 2, 3, 4. Soma esperada: 9.
int indiceL = 1; // Índice inicial (base 0 no array original)
int indiceR = 3; // Índice final (base 0 no array original)
int somaIntervalo = arraySomaPrefixos[indiceR + 1] - arraySomaPrefixos[indiceL];
}
Array de Diferenças
O array de diferenças é uma técnica utilizada para otimizar atualizações de intervalo em arrays. Dada uma sequência A = [a₀, a₁, ..., aₙ₋₁], seu array de diferenças D é construído tal que D[0] = A[0] e D[i] = A[i] - A[i-1] para i > 0.
A principal propriedade é que qualquer elemento A[k] pode ser reconstruído como a soma prefixa de D até k: A[k] = D[0] + D[1] + ... + D[k].
Uma atualização de intervalo, como adicionar um valor X a todos os elementos A[l] a A[r], pode ser realizada com apenas duas atualizações de ponto no array de diferenças: D[l] += X e D[r+1] -= X.
#include <vector>
#include <iostream>
// Demonstra a construção e uso de um array de diferenças para atualizações de intervalo.
void demonstrarArrayDiferencas() {
std::vector<int> originalValores = {0, 2, 5, 4, 9, 7, 10, 0};
int numElementos = originalValores.size();
// O array de diferenças tem tamanho N+1 para acomodar D[R+1] para o último elemento R=N-1.
std::vector<int> arrayDiferencas(numElementos + 1, 0);
// Construção inicial do array de diferenças
// D[0] = A[0]
// D[i] = A[i] - A[i-1] para i > 0
arrayDiferencas[0] = originalValores[0];
for (int i = 1; i < numElementos; ++i) {
arrayDiferencas[i] = originalValores[i] - originalValores[i - 1];
}
// Exemplo: Adicionar 'valorDelta' ao intervalo [indiceInicio, indiceFim]
int indiceInicio = 1; // Índice inicial (base 0 no array original)
int indiceFim = 4; // Índice final (base 0 no array original)
int valorDelta = 3;
// Aplica a atualização de intervalo como duas atualizações de ponto no array de diferenças.
if (indiceInicio < numElementos) {
arrayDiferencas[indiceInicio] += valorDelta;
}
if (indiceFim + 1 <= numElementos) { // Garante que o índice não exceda o tamanho
arrayDiferencas[indiceFim + 1] -= valorDelta;
}
// Reconstruir o array original a partir do array de diferenças para verificar o resultado.
std::vector<int> arrayReconstruido(numElementos);
for (int i = 0; i < numElementos; ++i) {
if (i == 0) {
arrayReconstruido[i] = arrayDiferencas[i];
} else {
arrayReconstruido[i] = arrayReconstruido[i - 1] + arrayDiferencas[i];
}
}
}
Árvore de Fenwick (Binary Indexed Tree - BIT)
A Árvore de Fenwick (ou BIT) é uma estrutura de dados eficiente para manter somas prefixas de uma sequência e realizar atualizações de ponto. Ela permite consultas de soma prefixa e atualizações de ponto em tempo logarítmico (O(logN)).
lowbit(x): Retorna o bit menos significativo dex. É calculado comox & (-x).- Atualização de Ponto: Para adicionar um valor
deltaValao elemento no índiceidx, percorremos os pais do nóidxna árvore, adicionandodeltaVala eles. - Consulta de Soma de Prefixo: Para consultar a soma dos elementos de 1 até
idx, percorremos os nós que contribuem para essa soma, que são os ancestrais deidxna "visão" da árvore de Fenwick.
#include <vector>
#include <iostream>
// Classe que implementa a Árvore de Fenwick para operações de ponto-modificar e prefixo-somar.
class ArvoreFenwick {
private:
std::vector<int> _arvore; // Armazena os valores cumulativos da Fenwick Tree
int _tamanho; // Tamanho máximo do array que a árvore pode representar
// Retorna o valor do bit menos significativo (Lowest Set Bit - LSB) de x.
int lowbit(int x) {
return x & (-x);
}
public:
// Construtor: inicializa a Fenwick Tree com um tamanho 'n'.
// Os índices na Fenwick Tree são baseados em 1.
ArvoreFenwick(int n) : _tamanho(n), _arvore(n + 1, 0) {}
// Adiciona 'deltaVal' ao elemento no índice 'idx' (base 1) e atualiza a árvore.
void adicionar(int idx, int deltaVal) {
for (int i = idx; i <= _tamanho; i += lowbit(i)) {
_arvore[i] += deltaVal;
}
}
// Calcula a soma dos elementos de 1 até 'idx' (base 1).
int consultarSomaPrefixos(int idx) {
int somaTotal = 0;
for (int i = idx; i > 0; i -= lowbit(i)) {
somaTotal += _arvore[i];
}
return somaTotal;
}
};
Exemplo 1: Atualização de Ponto, Consulta de Intervalo
Este cenário é o uso clássico da Árvore de Fenwick. Podemos atualizar o valor de um único elemento e consultar a soma de qualquer intervalo de elementos.
// Exemplo de uso principal para ArvoreFenwick (Ponto Atualização, Intervalo Consulta)
// Corresponde a problemas como Luogu P3374.
int main_exemplo1_fenwick_tree() {
int numElementos, numOperacoes; // N: tamanho do array, M: número de operações
std::cin >> numElementos >> numOperacoes;
ArvoreFenwick bit(numElementos); // Instancia a Fenwick Tree com 'numElementos'
// Inicializa a Fenwick Tree com os valores iniciais do array.
// Cada valor é adicionado como uma atualização de ponto.
for (int i = 1; i <= numElementos; ++i) {
int valorInicial;
std::cin >> valorInicial;
bit.adicionar(i, valorInicial); // Adiciona valor ao índice i (base 1)
}
// Processa as operações solicitadas.
for (int opContador = 0; opContador < numOperacoes; ++opContador) {
int tipoOperacao;
std::cin >> tipoOperacao;
if (tipoOperacao == 1) { // Tipo 1: Adicionar um valor a um ponto específico
int indice, valorIncremento;
std::cin >> indice >> valorIncremento;
bit.adicionar(indice, valorIncremento);
} else { // Tipo 2: Consultar a soma de um intervalo [indiceEsquerdo, indiceDireito]
int indiceEsquerdo, indiceDireito;
std::cin >> indiceEsquerdo >> indiceDireito;
// A soma do intervalo [L, R] é calculada como a soma prefixa até R menos a soma prefixa até L-1.
int somaIntervalo = bit.consultarSomaPrefixos(indiceDireito) - bit.consultarSomaPrefixos(indiceEsquerdo - 1);
std::cout << somaIntervalo << std::endl;
}
}
return 0;
}
Exemplo 2: Atualização de Intervalo, Consulta de Ponto
Para este cenário, a Árvore de Fenwick é aplicada sobre um array de diferenças. Uma atualização de intervalo no array original se traduz em duas atualizações de ponto no array de diferenças, e uma consulta de ponto no array original se torna uma consulta de soma prefixa no array de diferenças.
// Exemplo de uso principal para ArvoreFenwick (Intervalo Atualização, Ponto Consulta)
// Uma abordagem eficiente para problemas como Luogu P3368.
int main_exemplo2_fenwick_tree() {
int numElementos, numOperacoes;
std::cin >> numElementos >> numOperacoes;
// A Fenwick Tree neste caso opera sobre o array de diferenças.
// O tamanho é numElementos para permitir índices até numElementos.
ArvoreFenwick bitDiferencas(numElementos);
// O array original é necessário para calcular as diferenças iniciais.
std::vector<int> valoresOriginais(numElementos + 1, 0); // Índices base 1
// Inicializa a Fenwick Tree com as diferenças dos valores iniciais do array.
// D[i] = A[i] - A[i-1].
for (int i = 1; i <= numElementos; ++i) {
int valorAtual;
std::cin >> valorAtual;
bitDiferencas.adicionar(i, valorAtual - valoresOriginais[i-1]);
valoresOriginais[i] = valorAtual; // Armazena o valor atual para o próximo cálculo de diferença
}
// Processa as operações.
for (int opContador = 0; opContador < numOperacoes; ++opContador) {
int tipoOperacao;
std::cin >> tipoOperacao;
if (tipoOperacao == 1) { // Tipo 1: Atualizar um intervalo [indiceInicio, indiceFim] com um valor 'valorIncremento'
int indiceInicio, indiceFim, valorIncremento;
std::cin >> indiceInicio >> indiceFim >> valorIncremento;
// Adiciona 'valorIncremento' ao índice de início no array de diferenças.
bitDiferencas.adicionar(indiceInicio, valorIncremento);
// Subtrai 'valorIncremento' do índice (fim + 1) no array de diferenças, se ele estiver dentro dos limites.
if (indiceFim + 1 <= numElementos) {
bitDiferencas.adicionar(indiceFim + 1, -valorIncremento);
}
} else { // Tipo 2: Consultar o valor de um ponto específico (indiceConsulta)
int indiceConsulta;
std::cin >> indiceConsulta;
// O valor de um elemento A[x] é a soma prefixa dos elementos do array de diferenças até x.
std::cout << bitDiferencas.consultarSomaPrefixos(indiceConsulta) << std::endl;
}
}
return 0;
}
Ordenação por Mesclagem (Merge Sort)
O Merge Sort é um algoritmo de ordenação eficiente baseado no paradigma "dividir para conquistar". Ele divide um array em duas metades, ordena recursivamente cada metade e, em seguida, mescla as metades ordenadas. Além de ordenar, pode ser estendido para contar o número de pares inversos em um array.
- Pares Inversos: Um par
(i, j)é um par inverso sei < jeA[i] > A[j]. - Durante a fase de mesclagem, quando um elemento da metade direita é escolhido antes de um elemento da metade esquerda, todos os elementos restantes na metade esquerda formam um par inverso com o elemento da direita.
#include <iostream>
#include <vector>
#include <algorithm> // Para std::copy, se usado
// Variável global para manter a contagem de pares inversos.
long long contadorInversoes = 0;
// Função auxiliar para mesclar duas sub-arrays ordenadas e contar inversões.
void mesclarArrays(std::vector<int>& vetorDados, int idxEsquerdo, int idxMeio, int idxDireito) {
// Cria um vetor temporário para armazenar a sub-array mesclada.
std::vector<int> vetorTemporario(idxDireito - idxEsquerdo + 1);
int p1 = idxEsquerdo; // Ponteiro para o início da primeira sub-array [idxEsquerdo, idxMeio]
int p2 = idxMeio + 1; // Ponteiro para o início da segunda sub-array [idxMeio + 1, idxDireito]
int pTemp = 0; // Ponteiro para o vetorTemporario
while (p1 <= idxMeio && p2 <= idxDireito) {
if (vetorDados[p1] <= vetorDados[p2]) {
vetorTemporario[pTemp++] = vetorDados[p1++];
} else {
vetorTemporario[pTemp++] = vetorDados[p2++];
// Se um elemento da direita é menor que um elemento da esquerda,
// então ele forma um par inverso com todos os elementos restantes na esquerda.
contadorInversoes += (idxMeio - p1 + 1);
}
}
// Copia quaisquer elementos restantes da primeira sub-array.
while (p1 <= idxMeio) {
vetorTemporario[pTemp++] = vetorDados[p1++];
}
// Copia quaisquer elementos restantes da segunda sub-array.
while (p2 <= idxDireito) {
vetorTemporario[pTemp++] = vetorDados[p2++];
}
// Copia os elementos ordenados do vetorTemporario de volta para o vetorDados original.
for (int i = 0; i < vetorTemporario.size(); ++i) {
vetorDados[idxEsquerdo + i] = vetorTemporario[i];
}
}
// Implementação principal do algoritmo de Ordenação por Mesclagem.
void ordenacaoPorMesclagem(std::vector<int>& vetorDados, int idxEsquerdo, int idxDireito) {
if (idxEsquerdo < idxDireito) {
int idxMeio = idxEsquerdo + (idxDireito - idxEsquerdo) / 2; // Evita overflow para grandes valores de (l+r)
// Recursivamente ordena as duas metades.
ordenacaoPorMesclagem(vetorDados, idxEsquerdo, idxMeio);
ordenacaoPorMesclagem(vetorDados, idxMeio + 1, idxDireito);
// Mescla as metades ordenadas e atualiza a contagem de inversões.
mesclarArrays(vetorDados, idxEsquerdo, idxMeio, idxDireito);
}
}
// Exemplo de uso principal para ordenacaoPorMesclagem e contagem de inversões.
int main_merge_sort() {
int nElementos;
std::cin >> nElementos;
std::vector<int> meuArray(nElementos);
for (int i = 0; i < nElementos; ++i) {
std::cin >> meuArray[i];
}
ordenacaoPorMesclagem(meuArray, 0, nElementos - 1);
std::cout << contadorInversoes << std::endl;
return 0;
}
Somas de Prefixo 2D (Matriz de Soma Cumulativa)
Extensão do conceito de soma de prefixos para matrizes bidimensionais. Permite calcular a soma de elementos em qualquer submatriz retangular em tempo constante (O(1)) após uma pré-computação O(M*N).
Dada uma matriz Matrix[i][j], a matriz de soma de prefixos S[i][j] armazena a soma de todos os elementos na submatriz do canto superior esquerdo (0,0) até (i-1, j-1) da matriz original. Para facilitar os cálculos, a matriz S geralmante tem uma linha e uma coluna extra de zeros.
A fórmula para calcular S[i+1][j+1] (considerando S com +1 nas dimensões para o offset de 0-base) é:
S[i+1][j+1] = Matrix[i][j] + S[i][j+1] + S[i+1][j] - S[i][j]
Para obter a soma de uma submatriz entre (r1, c1) e (r2, c2) (inclusive, índices 0-base na matriz original):
Soma = S[r2+1][c2+1] - S[r1][c2+1] - S[r2+1][c1] + S[r1][c1]
#include <vector>
#include <iostream>
// Demonstra a construção e uso de uma matriz de soma de prefixos 2D.
void demonstrarSomaPrefixos2D() {
std::vector<std::vector<int>> matrizOriginal = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int numLinhas = matrizOriginal.size();
int numColunas = matrizOriginal[0].size();
// Cria a matriz de soma de prefixos 2D com dimensões (numLinhas+1) x (numColunas+1)
// para simplificar o manuseio de índices e as fórmulas.
std::vector<std::vector<int>> somaPrefixos2D(numLinhas + 1, std::vector<int>(numColunas + 1, 0));
// Preenche a matriz de soma de prefixos.
// somaPrefixos2D[i+1][j+1] armazena a soma da região (0,0) a (i,j) da matriz original.
for (int i = 0; i < numLinhas; ++i) {
for (int j = 0; j < numColunas; ++j) {
somaPrefixos2D[i + 1][j + 1] = matrizOriginal[i][j] + somaPrefixos2D[i][j + 1] +
somaPrefixos2D[i + 1][j] - somaPrefixos2D[i][j];
}
}
// Exemplo de uso: Calcular a soma de uma submatriz (linha1, col1) a (linha2, col2)
// Usando índices base 0 para a matriz original.
// Submatriz de (0,0) a (1,1) (inclusive) da matriz original: {{1,2},{4,5}}. Soma = 12.
int r1 = 0, c1 = 0; // Coordenada superior esquerda da submatriz (base 0)
int r2 = 1, c2 = 1; // Coordenada inferior direita da submatriz (base 0)
int somaSubmatriz = somaPrefixos2D[r2 + 1][c2 + 1] - somaPrefixos2D[r1][c2 + 1] -
somaPrefixos2D[r2 + 1][c1] + somaPrefixos2D[r1][c1];
}
Template de Conjunto Disjunto (Union-Find)
O Union-Find é uma estrutura de dados utilizada para manter um conjunto de elementos divididos em um número de subconjuntos disjuntos (não sobrepostos). Ele suporta duas operações principais:
find: Determina a qual subconjunto um elemento pertence. Retorna o "representante" (ou "raiz") desse subconjunto.union(oujoin): Une dois subconjuntos em um único subconjunto.
As otimizações comuns incluem "compressão de caminho" no find e "união por rank/tamanho" no union para melhorar o desempenho para quase tempo constante amortizado.
#include <vector>
#include <numeric> // Para std::iota (para inicialização)
// Implementação da estrutura de dados Union-Find (Conjuntos Disjuntos).
class ConjuntoDisjunto {
public:
std::vector<int> vetorPais; // Armazena o pai de cada elemento.
// Se vetorPais[i] == i, então i é o representante de seu conjunto.
// Construtor: Inicializa 'n' elementos. Cada elemento é inicialmente seu próprio representante.
explicit ConjuntoDisjunto(int n) {
vetorPais.resize(n);
std::iota(vetorPais.begin(), vetorPais.end(), 0); // Preenche com 0, 1, 2, ..., n-1
}
// Encontra o representante (raiz) do conjunto ao qual 'elemento' pertence.
// Aplica compressão de caminho: durante a busca, cada nó no caminho aponta diretamente para a raiz.
int encontrarRepresentante(int elemento) {
if (elemento == vetorPais[elemento]) {
return elemento; // 'elemento' é o representante de seu próprio conjunto
}
// Recursivamente encontra o representante e atualiza o pai para compressão de caminho.
return vetorPais[elemento] = encontrarRepresentante(vetorPais[elemento]);
}
// Verifica se dois elementos pertencem ao mesmo conjunto.
bool saoConectados(int elementoX, int elementoY) {
return encontrarRepresentante(elementoX) == encontrarRepresentante(elementoY);
}
// Une os conjuntos aos quais 'elementoX' e 'elementoY' pertencem.
// Simplesmente faz o representante de um conjunto apontar para o outro.
void unirConjuntos(int elementoX, int elementoY) {
int representanteX = encontrarRepresentante(elementoX);
int representanteY = encontrarRepresentante(elementoY);
if (representanteX != representanteY) {
vetorPais[representanteY] = representanteX; // O representante de Y agora aponta para o de X
}
}
};