Segment Tree em Rust: Consultas em Intervalos

A Segment Tree (Árvore de Segmentos) é uma estrutura de dados que permite realizar consultas e atualizações em intervalos de um array em tempo O(log n). Ela é essencial para problemas como: “qual é a soma dos elementos do índice 2 ao 7?” ou “qual é o mínimo entre as posições 3 e 10?”. Com lazy propagation, também suporta atualizações em intervalos inteiros de forma eficiente.

Conceito e Teoria

O Problema de Range Query

Dado um array de n elementos, queremos responder repetidamente:

Range Query: qual é o resultado de uma operação (soma, mínimo, máximo, GCD…) em um intervalo [l, r]?
Point Update: atualizar o valor em uma posição específica
Range Update: atualizar todos os valores em um intervalo [l, r]

  Array:  [2, 5, 1, 4, 9, 3, 7, 6]

  Consulta soma [1, 5]:
  5 + 1 + 4 + 9 + 3 = 22

  Sem Segment Tree: O(n) por consulta
  Com Segment Tree: O(log n) por consulta!

Estrutura da Árvore

A Segment Tree divide o array recursivamente em metades, armazenando o resultado da operação em cada nó:

  Array original: [2, 5, 1, 4, 9, 3, 7, 6]
  Índices:         0  1  2  3  4  5  6  7

  Segment Tree (soma):

                        [37]                    nó 1: soma [0,7]
                       /    \
                  [12]        [25]              nós 2,3: [0,3] e [4,7]
                 /    \      /    \
              [7]     [5]  [12]   [13]          nós 4-7: pares
             /  \    / \   / \    / \
           [2] [5] [1][4] [9][3] [7][6]        nós 8-15: folhas

  Cada nó armazena a soma do seu intervalo.
  Nó i tem filhos 2*i (esquerdo) e 2*i+1 (direito).

Operação de Consulta (Query)

  Consulta soma [2, 5] no array [2, 5, 1, 4, 9, 3, 7, 6]:

                        [37] [0,7]
                       /    \
                  [12] [0,3] [25] [4,7]
                 /    \      /    \
              [7]    [5]  [12]   [13]
  [0,1]      /  \    / \   / \    / \   [6,7]
           [2] [5] [1][4] [9][3] [7][6]
                    ^  ^   ^  ^
                   [2][3] [4][5]   <- intervalo [2,5]

  Combinamos: [1] + [4] + [9] + [3] = 17
  Ou pelo nó [5] (soma [2,3]) + [12] (soma [4,5]) = 5 + 12 = 17

Operação de Atualização (Update)

  Atualizar posição 3: valor 4 -> 10

  Apenas os nós no caminho da folha até a raiz são atualizados:

                     [37]->[43]                   +6 em cada nó
                       /    \                      no caminho
                [12]->[18]   [25]
                 /    \
              [7]  [5]->[11]
                    / \
                  [1] [4]->[10]   <- folha atualizada

  Apenas O(log n) = 3 nós atualizados (não o array inteiro!)

Lazy Propagation

Para atualizações em intervalos, usamos “preguiça” – adiamos as atualizações até que sejam necessárias:

  "Some 5 a todos os elementos em [0, 3]"

  SEM lazy: atualiza 4 folhas = O(n)
  COM lazy: marca o nó [0,3] como "pendente +5"

                        [37]
                       /    \
                  [12]       [25]
                 lazy:+5
                 /    \
              [7]     [5]      <- Não atualiza agora!
             /  \    / \
           [2] [5] [1][4]     <- Folhas não tocadas

  Quando uma consulta ou atualização precisar descer abaixo de [0,3],
  a propagação acontece naquele momento ("push down").

Complexidade

Operação	Complexidade	Observação
Construir	O(n)	Percorre cada elemento uma vez
Consulta (query)	O(log n)	Visita O(log n) nós
Atualização pontual	O(log n)	Atualiza caminho raiz-folha
Atualização em intervalo	O(log n)	Com lazy propagation
Espaço	O(n)	Exatamente 4n (ou 2próxima pot.

Implementação em Rust

Segment Tree para Soma com Atualização Pontual

/// Segment Tree para consultas de soma em intervalos.
/// Suporta atualização pontual e consulta de intervalo em O(log n).
struct SegmentTree {
    /// Array interno da árvore (indexado a partir de 1)
    arvore: Vec<i64>,
    /// Tamanho do array original
    n: usize,
}

impl SegmentTree {
    /// Constrói a Segment Tree a partir de um array.
    fn construir(dados: &[i64]) -> Self {
        let n = dados.len();
        let mut arvore = vec![0i64; 4 * n]; // Espaço suficiente

        fn build(arvore: &mut Vec<i64>, dados: &[i64], no: usize, inicio: usize, fim: usize) {
            if inicio == fim {
                // Nó folha: armazena o valor diretamente
                arvore[no] = dados[inicio];
                return;
            }

            let meio = (inicio + fim) / 2;
            build(arvore, dados, 2 * no, inicio, meio);       // Filho esquerdo
            build(arvore, dados, 2 * no + 1, meio + 1, fim);  // Filho direito

            // O nó pai armazena a soma dos filhos
            arvore[no] = arvore[2 * no] + arvore[2 * no + 1];
        }

        if n > 0 {
            build(&mut arvore, dados, 1, 0, n - 1);
        }

        SegmentTree { arvore, n }
    }

    /// Consulta a soma no intervalo [l, r] (0-indexado).
    fn consultar(&self, l: usize, r: usize) -> i64 {
        fn query(arvore: &[i64], no: usize, inicio: usize, fim: usize, l: usize, r: usize) -> i64 {
            // Caso 1: intervalo completamente fora
            if r < inicio || fim < l {
                return 0; // Elemento neutro da soma
            }

            // Caso 2: intervalo completamente dentro
            if l <= inicio && fim <= r {
                return arvore[no];
            }

            // Caso 3: intervalo parcialmente sobreposto
            let meio = (inicio + fim) / 2;
            let esq = query(arvore, 2 * no, inicio, meio, l, r);
            let dir = query(arvore, 2 * no + 1, meio + 1, fim, l, r);
            esq + dir
        }

        if self.n == 0 {
            return 0;
        }
        query(&self.arvore, 1, 0, self.n - 1, l, r)
    }

    /// Atualiza o valor na posição pos para novo_valor.
    fn atualizar(&mut self, pos: usize, novo_valor: i64) {
        fn update(
            arvore: &mut Vec<i64>,
            no: usize,
            inicio: usize,
            fim: usize,
            pos: usize,
            valor: i64,
        ) {
            if inicio == fim {
                arvore[no] = valor;
                return;
            }

            let meio = (inicio + fim) / 2;
            if pos <= meio {
                update(arvore, 2 * no, inicio, meio, pos, valor);
            } else {
                update(arvore, 2 * no + 1, meio + 1, fim, pos, valor);
            }

            // Recalcula o nó pai
            arvore[no] = arvore[2 * no] + arvore[2 * no + 1];
        }

        update(&mut self.arvore, 1, 0, self.n - 1, pos, novo_valor);
    }
}

Segment Tree com Lazy Propagation

/// Segment Tree com Lazy Propagation para atualizações em intervalos.
/// Suporta: somar um valor a todo um intervalo [l, r] em O(log n).
struct SegmentTreeLazy {
    arvore: Vec<i64>,
    lazy: Vec<i64>,     // Atualizações pendentes
    n: usize,
}

impl SegmentTreeLazy {
    fn construir(dados: &[i64]) -> Self {
        let n = dados.len();
        let mut st = SegmentTreeLazy {
            arvore: vec![0; 4 * n],
            lazy: vec![0; 4 * n],
            n,
        };

        if n > 0 {
            st.build(dados, 1, 0, n - 1);
        }
        st
    }

    fn build(&mut self, dados: &[i64], no: usize, inicio: usize, fim: usize) {
        if inicio == fim {
            self.arvore[no] = dados[inicio];
            return;
        }
        let meio = (inicio + fim) / 2;
        self.build(dados, 2 * no, inicio, meio);
        self.build(dados, 2 * no + 1, meio + 1, fim);
        self.arvore[no] = self.arvore[2 * no] + self.arvore[2 * no + 1];
    }

    /// Propaga a atualização pendente para os filhos ("push down")
    fn propagar(&mut self, no: usize, inicio: usize, fim: usize) {
        if self.lazy[no] != 0 {
            let meio = (inicio + fim) / 2;

            // Atualiza os filhos
            self.arvore[2 * no] += self.lazy[no] * (meio - inicio + 1) as i64;
            self.arvore[2 * no + 1] += self.lazy[no] * (fim - meio) as i64;

            // Passa a preguiça para os filhos
            self.lazy[2 * no] += self.lazy[no];
            self.lazy[2 * no + 1] += self.lazy[no];

            // Limpa a preguiça do nó atual
            self.lazy[no] = 0;
        }
    }

    /// Soma `valor` a todos os elementos no intervalo [l, r].
    fn atualizar_intervalo(&mut self, l: usize, r: usize, valor: i64) {
        self.update_range(1, 0, self.n - 1, l, r, valor);
    }

    fn update_range(
        &mut self,
        no: usize,
        inicio: usize,
        fim: usize,
        l: usize,
        r: usize,
        valor: i64,
    ) {
        if r < inicio || fim < l {
            return; // Fora do intervalo
        }

        if l <= inicio && fim <= r {
            // Intervalo completamente coberto: aplica lazy
            self.arvore[no] += valor * (fim - inicio + 1) as i64;
            self.lazy[no] += valor;
            return;
        }

        // Propaga antes de descer
        self.propagar(no, inicio, fim);

        let meio = (inicio + fim) / 2;
        self.update_range(2 * no, inicio, meio, l, r, valor);
        self.update_range(2 * no + 1, meio + 1, fim, l, r, valor);

        self.arvore[no] = self.arvore[2 * no] + self.arvore[2 * no + 1];
    }

    /// Consulta a soma no intervalo [l, r].
    fn consultar(&mut self, l: usize, r: usize) -> i64 {
        self.query_range(1, 0, self.n - 1, l, r)
    }

    fn query_range(
        &mut self,
        no: usize,
        inicio: usize,
        fim: usize,
        l: usize,
        r: usize,
    ) -> i64 {
        if r < inicio || fim < l {
            return 0;
        }

        if l <= inicio && fim <= r {
            return self.arvore[no];
        }

        self.propagar(no, inicio, fim);

        let meio = (inicio + fim) / 2;
        let esq = self.query_range(2 * no, inicio, meio, l, r);
        let dir = self.query_range(2 * no + 1, meio + 1, fim, l, r);
        esq + dir
    }
}

Segment Tree Genérica para Mínimo

/// Segment Tree para consultas de mínimo em intervalos (Range Minimum Query).
struct SegmentTreeMin {
    arvore: Vec<i64>,
    n: usize,
}

impl SegmentTreeMin {
    fn construir(dados: &[i64]) -> Self {
        let n = dados.len();
        let mut arvore = vec![i64::MAX; 4 * n];

        fn build(arvore: &mut Vec<i64>, dados: &[i64], no: usize, inicio: usize, fim: usize) {
            if inicio == fim {
                arvore[no] = dados[inicio];
                return;
            }
            let meio = (inicio + fim) / 2;
            build(arvore, dados, 2 * no, inicio, meio);
            build(arvore, dados, 2 * no + 1, meio + 1, fim);
            arvore[no] = arvore[2 * no].min(arvore[2 * no + 1]); // Mínimo!
        }

        if n > 0 {
            build(&mut arvore, dados, 1, 0, n - 1);
        }
        SegmentTreeMin { arvore, n }
    }

    fn consultar_minimo(&self, l: usize, r: usize) -> i64 {
        fn query(arvore: &[i64], no: usize, inicio: usize, fim: usize, l: usize, r: usize) -> i64 {
            if r < inicio || fim < l {
                return i64::MAX; // Elemento neutro do mínimo
            }
            if l <= inicio && fim <= r {
                return arvore[no];
            }
            let meio = (inicio + fim) / 2;
            let esq = query(arvore, 2 * no, inicio, meio, l, r);
            let dir = query(arvore, 2 * no + 1, meio + 1, fim, l, r);
            esq.min(dir)
        }

        if self.n == 0 { return i64::MAX; }
        query(&self.arvore, 1, 0, self.n - 1, l, r)
    }
}

Exemplo Prático: Sistema de Análise de Temperaturas

fn main() {
    // === Segment Tree para Soma ===
    println!("=== Análise de Temperaturas Diárias ===\n");

    // Temperaturas médias diárias (em °C x 10 para usar inteiros)
    let temperaturas: Vec<i64> = vec![225, 240, 195, 280, 310, 255, 200, 185,
                                       270, 295, 320, 290, 245, 210, 190];
    // Representam: 22.5, 24.0, 19.5, 28.0, 31.0, 25.5, 20.0, 18.5, ...

    let n = temperaturas.len();
    let mut st = SegmentTree::construir(&temperaturas);

    // Soma de temperaturas na primeira semana (índices 0-6)
    let soma_semana1 = st.consultar(0, 6);
    println!("Soma das temperaturas (semana 1): {:.1}°C", soma_semana1 as f64 / 10.0);
    println!("Média da semana 1: {:.1}°C", soma_semana1 as f64 / 70.0);

    // Soma da segunda semana
    let soma_semana2 = st.consultar(7, 13);
    println!("Média da semana 2: {:.1}°C", soma_semana2 as f64 / 70.0);

    // Atualiza temperatura do dia 3 (correção de sensor)
    println!("\nCorrigindo temperatura do dia 4: 28.0 -> 26.5°C");
    st.atualizar(3, 265);
    let nova_soma = st.consultar(0, 6);
    println!("Nova média da semana 1: {:.1}°C", nova_soma as f64 / 70.0);

    // === Segment Tree para Mínimo ===
    println!("\n=== Consulta de Temperatura Mínima ===\n");

    let st_min = SegmentTreeMin::construir(&temperaturas);

    let min_semana1 = st_min.consultar_minimo(0, 6);
    println!("Menor temperatura da semana 1: {:.1}°C", min_semana1 as f64 / 10.0);

    let min_total = st_min.consultar_minimo(0, n - 1);
    println!("Menor temperatura do período: {:.1}°C", min_total as f64 / 10.0);

    // Consultas variadas
    for (l, r) in [(0, 3), (4, 7), (8, 11), (12, 14)] {
        let min = st_min.consultar_minimo(l, r);
        let soma = st.consultar(l, r);
        let qtd = (r - l + 1) as f64;
        println!(
            "  Dias {}-{}: min={:.1}°C, média={:.1}°C",
            l + 1, r + 1,
            min as f64 / 10.0,
            soma as f64 / (qtd * 10.0)
        );
    }

    // === Lazy Propagation ===
    println!("\n=== Lazy Propagation: Ajuste em Lote ===\n");

    let vendas: Vec<i64> = vec![100, 150, 200, 120, 180, 160, 140, 190];
    let mut st_lazy = SegmentTreeLazy::construir(&vendas);

    println!("Vendas totais (dias 1-4): {}", st_lazy.consultar(0, 3));
    println!("Vendas totais (dias 5-8): {}", st_lazy.consultar(4, 7));

    // Promoção: +50 unidades vendidas nos dias 3-6
    println!("\nAplicando promoção nos dias 3-6 (+50 unidades)...");
    st_lazy.atualizar_intervalo(2, 5, 50);

    println!("Vendas totais (dias 1-4): {}", st_lazy.consultar(0, 3));
    println!("Vendas totais (dias 5-8): {}", st_lazy.consultar(4, 7));
    println!("Vendas totais (todos): {}", st_lazy.consultar(0, 7));
}

Exercícios

Exercício 1: Range Maximum Query

Implemente uma Segment Tree para consultas de máximo em intervalos. Suporte atualização pontual e consulta de máximo.

struct SegmentTreeMax {
    arvore: Vec<i64>,
    n: usize,
}

impl SegmentTreeMax {
    fn construir(dados: &[i64]) -> Self { todo!() }
    fn consultar_maximo(&self, l: usize, r: usize) -> i64 { todo!() }
    fn atualizar(&mut self, pos: usize, valor: i64) { todo!() }
}

Exercício 2: Segment Tree com GCD

Implemente uma Segment Tree que computa o MDC (Máximo Divisor Comum / GCD) de um intervalo. A operação de combinação é gcd(a, b) em vez de soma ou min.

fn gcd(a: i64, b: i64) -> i64 {
    if b == 0 { a.abs() } else { gcd(b, a % b) }
}

struct SegmentTreeGCD {
    arvore: Vec<i64>,
    n: usize,
}

impl SegmentTreeGCD {
    fn construir(dados: &[i64]) -> Self { todo!() }
    fn consultar_gcd(&self, l: usize, r: usize) -> i64 { todo!() }
    fn atualizar(&mut self, pos: usize, valor: i64) { todo!() }
}

// Teste:
// dados = [12, 8, 6, 18, 24]
// gcd([0, 2]) = gcd(12, 8, 6) = 2
// gcd([2, 4]) = gcd(6, 18, 24) = 6

Exercício 3: Segment Tree com Atribuição em Intervalo

Modifique a Segment Tree com lazy propagation para suportar a operação de atribuição em vez de soma: “defina todos os elementos em [l, r] como o valor x”.

struct SegmentTreeAtribuicao {
    arvore: Vec<i64>,
    lazy: Vec<Option<i64>>,  // None = sem pendência, Some(x) = definir como x
    n: usize,
}

impl SegmentTreeAtribuicao {
    fn construir(dados: &[i64]) -> Self { todo!() }
    fn atribuir_intervalo(&mut self, l: usize, r: usize, valor: i64) { todo!() }
    fn consultar_soma(&mut self, l: usize, r: usize) -> i64 { todo!() }
}

Conclusão

A Segment Tree e uma estrutura fundamental para problemas que envolvem:

Consultas em intervalos (soma, minimo, maximo, GCD, etc.) em O(log n)
Atualizacoes pontuais em O(log n) – muito melhor que O(n) de forca bruta
Atualizacoes em intervalos com lazy propagation em O(log n)
Persistencia: versoes anteriores podem ser mantidas com Segment Tree persistente

E amplamente utilizada em programacao competitiva, sistemas de banco de dados (range queries), analise de series temporais e computacao geometrica. Embora a implementacao seja mais extensa que a Fenwick Tree (proxima pagina), a Segment Tree e mais geral e pode resolver qualquer problema de range query que combine com uma operacao associativa.

Conteudo produzido pela Equipe Rust Brasil para rustlang.com.br