As árvores de segmento representam um avançado conceito em estruturas de dados, frequentemente classificadas como problemas de dificuldade elevada.

Essencialmente, as árvores de segmento são uma aplicação clássica do princípio de troca de espaço por tempo, utilizando uma estrutura unidimensional para otimizar operações que seriam de ordem temporal superior. A eficácia dessa abordagem depende de características específicas na organização dos dados.

Uma excelente explicação sobre o tema pode ser encontrada em: https://www.acwing.com/blog/content/3369/

O termo "árvore" no nome dessas estruturas reflete sua natureza hierárquica. As árvores de segmento são especialmente projetadas para resolver problemas de intervalos, incluindo desafios como RMQ (Range Minimum Query) e RSQ (Range Sum Query).

Cada nó filho representa um subintervalo da sequência completa, enquanto os nós folha representam informações de elementos individuais. A enformação flui dos nós filhos para seus resepctivos pais, que armazenam uma agregação desses dados.

Árvores de segmento são a versão em árvore do conceito de divisão em blocos, ou uma abordagem binária para processamento de informações, alcançando uma complexidade de O(log n). Em cnotraste, a abordagem de divisão em blocos pode ser resumida como: dividir a sequência completa em blocos menores, de forma que qualquer consulta de intervalo possa ser expressa como a união de k blocos completos e m elementos individuais (0 ≤ k, m ≤ √n). Contudo, a divisão em blocos comum não resolve eficientemente muitos problemas, levando ao desenvolvimento das árvores de segmento com complexidade logarítmica.

Se você está apenas buscando uma solução que passe nos testes dos problemas 303 e 307 do LeetCode, esses desafios podem não merecer seu esforço. Na verdade, seu propósito é servir como exercício prático para dominar árvores de segmento.

Problema 303: Soma de Intervalo - Array Imutável

Dado um array de inteiros nums, processe múltiplos consultas do seguinte tipo:

1. Calcular a soma dos elementos de nums entre os índices left e right (inclusive), onde left <= right

Implemente a classe SomaArray:

• SomaArray(int\[\] nums): inicializa o objeto com o array nums
• int somaIntervalo(int i, int j): retorna a soma total dos elementos de nums entre os índices left e right (inclusive), ou seja, nums\[left\] + nums\[left + 1\] + ... + nums\[right\]

Exemplo 1:

Entrada:
["SomaArray", "somaIntervalo", "somaIntervalo", "somaIntervalo"]
[[-2, 0, 3, -5, 2, -1], [0, 2], [2, 5], [0, 5]]
Saída:
[nulo, 1, -1, -3]

Explicação:
SomaArray somaArray = new SomaArray([-2, 0, 3, -5, 2, -1]);
somaArray.somaIntervalo(0, 2); // retorna 1 ((-2) + 0 + 3)
somaArray.somaIntervalo(2, 5); // retorna -1 (3 + (-5) + 2 + (-1)) 
somaArray.somaIntervalo(0, 5); // retorna -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

Este problema é essencialmente um modelo para implementação de árvore de segmento, focando principalmente na construção e consulta da estrutura.

class SomaArray { private: struct No { int soma = 0; long long limiteEsquerdo = -999; long long limiteDireito = -999; } nos[1000000];

vector<int> sequencia;
int resultado = 0;

void construir(int no, int esquerda, int direita) {
    nos[no].limiteEsquerdo = esquerda;
    nos[no].limiteDireito = direita;
    
    if(esquerda == direita) {
        nos[no].soma = sequencia[esquerda];
        return;
    }
    
    int meio = (esquerda + direita) / 2;
    construir(2 * no, esquerda, meio);
    construir(2 * no + 1, meio + 1, direita);
    nos[no].soma = nos[2 * no].soma + nos[2 * no + 1].soma;
}

void buscarSoma(int no, int inicio, int fim) {
    if(nos[no].limiteEsquerdo >= inicio && nos[no].limiteDireito <= fim) {
        resultado += nos[no].soma;
        return;
    }
    
    int meio = (nos[no].limiteEsquerdo + nos[no].limiteDireito) >> 1;
    if(inicio <= meio) buscarSoma(2 * no, inicio, fim);
    if(fim > meio) buscarSoma(2 * no + 1, inicio, fim);
}

public: SomaArray(vector& nums) { sequencia.push_back(0); for(int i = 0; i < nums.size(); i++) { sequencia.push_back(nums[i]); } if(!nums.empty()) construir(1, 1, nums.size()); }

int somaIntervalo(int i, int j) {
    buscarSoma(1, i + 1, j + 1);
    int final = resultado;
    resultado = 0;
    return final;
}

};

/**

• Seu objeto SomaArray será instanciado e chamado da seguinte forma:
• SomaArray* obj = new SomaArray(nums);
• int param_1 = obj->somaIntervalo(i,j); */

</div>Problema 307: Soma de Intervalo - Array Mutável
-----------------------------------------------

Dado um array `nums`, você deve implementar dois tipos de operações:

1. Atualizar o valor em um índice específico do array `nums`
2. Retornar a soma dos elementos entre os índices `left` e `right` (inclusive), onde `left &lt;= right`

Implemente a classe `SomaArrayMutavel`:

- `SomaArrayMutavel(int\[\] nums)`: inicializa o objeto com o array de inteiros `nums`
- `void atualizar(int indice, int valor)`: atualiza o valor de `nums\[indice\]` para `valor`
- `int somaIntervalo(int esquerda, int direita)`: retorna a soma dos elementos entre os índices `left` e `right` (inclusive)

Exemplo 1:

Entrada: ["SomaArrayMutavel", "somaIntervalo", "atualizar", "somaIntervalo"] [[[1, 3, 5]], [0, 2], [1, 2], [0, 2]] Saída: [nulo, 9, nulo, 8]

Explicação: SomaArrayMutavel somaArray = new SomaArrayMutavel([1, 3, 5]); somaArray.somaIntervalo(0, 2); // retorna 1 + 3 + 5 = 9 somaArray.atualizar(1, 2); // nums = [1,2,5] somaArray.somaIntervalo(0, 2); // retorna 1 + 2 + 5 = 8

Este problema é um modelo clássico para implementação de árvores de segmento com suporte a atualizações.

<div>```

class SomaArrayMutavel {
private:
    struct No {
        int soma = 0;
        long long limiteEsquerdo = -999;
        long long limiteDireito = -999;
    } estrutura[100000];

    vector<int> dados;
    int acumulador = 0;
    
    void construir(int no, int esquerda, int direita) {
        estrutura[no].limiteEsquerdo = esquerda;
        estrutura[no].limiteDireito = direita;
        
        if(esquerda == direita) {
            estrutura[no].soma = dados[esquerda];
            return;
        }
        
        int meio = (esquerda + direita) / 2;
        construir(2 * no, esquerda, meio);
        construir(2 * no + 1, meio + 1, direita);
        estrutura[no].soma = estrutura[2 * no].soma + estrutura[2 * no + 1].soma;
    }
    
    void buscarSoma(int no, int inicio, int fim) {
        if(estrutura[no].limiteEsquerdo >= inicio && estrutura[no].limiteDireito <= fim) {
            acumulador += estrutura[no].soma;
            return;
        }
        
        int meio = (estrutura[no].limiteEsquerdo + estrutura[no].limiteDireito) >> 1;
        if(inicio <= meio) buscarSoma(2 * no, inicio, fim);
        if(fim > meio) buscarSoma(2 * no + 1, inicio, fim);
    }
    
    void modificar(int posicao, int no, int valor) {
        if(estrutura[no].limiteEsquerdo == estrutura[no].limiteDireito) {
            estrutura[no].soma = valor;
            return;
        }
        
        int meio = (estrutura[no].limiteEsquerdo + estrutura[no].limiteDireito) / 2;
        if(posicao <= meio) modificar(posicao, 2 * no, valor);
        else modificar(posicao, 2 * no + 1, valor);
        estrutura[no].soma = estrutura[2 * no].soma + estrutura[2 * no + 1].soma;
    }

public:
    SomaArrayMutavel(vector<int>& nums) {
        dados.push_back(0);
        for(int i = 0; i < nums.size(); i++) {
            dados.push_back(nums[i]);
        }
        if(!nums.empty()) construir(1, 1, nums.size());
    }
    
    void atualizar(int indice, int valor) {
        modificar(indice + 1, 1, valor);
    }
    
    int somaIntervalo(int i, int j) {
        acumulador = 0;
        buscarSoma(1, i + 1, j + 1);
        return acumulador;
    }
};

/**
 * Seu objeto SomaArrayMutavel será instanciado e chamado da seguinte forma:
 * SomaArrayMutavel* obj = new SomaArrayMutavel(nums);
 * int param_1 = obj->somaIntervalo(i,j);
 */
</int></int>