Fenwick Tree (BIT) em Rust: Árvore Indexada Binária

/// Fenwick Tree (Binary Indexed Tree).
/// Suporta prefix sum query e point update em O(log n).
struct FenwickTree {
    /// Array interno (1-indexado, posição 0 não é usada)
    bit: Vec<i64>,
    /// Tamanho do array original
    n: usize,
}

impl FenwickTree {
    /// Cria uma Fenwick Tree para um array de tamanho n (inicializado com zeros).
    fn novo(n: usize) -> Self {
        FenwickTree {
            bit: vec![0; n + 1],
            n,
        }
    }

    /// Constrói a Fenwick Tree a partir de um array existente em O(n).
    fn construir(dados: &[i64]) -> Self {
        let n = dados.len();
        let mut bit = vec![0i64; n + 1];

        // Copia os dados (1-indexado)
        for i in 0..n {
            bit[i + 1] = dados[i];
        }

        // Propagação eficiente em O(n)
        for i in 1..=n {
            let pai = i + lowbit(i);
            if pai <= n {
                bit[pai] += bit[i];
            }
        }

        FenwickTree { bit, n }
    }

    /// Atualiza: a[pos] += delta (pos é 1-indexado)
    fn atualizar(&mut self, mut pos: usize, delta: i64) {
        while pos <= self.n {
            self.bit[pos] += delta;
            pos += lowbit(pos);
        }
    }

    /// Consulta a soma do prefixo: a[1] + a[2] + ... + a[pos]
    fn prefix_sum(&self, mut pos: usize) -> i64 {
        let mut soma: i64 = 0;
        while pos > 0 {
            soma += self.bit[pos];
            pos -= lowbit(pos);
        }
        soma
    }

    /// Consulta a soma do intervalo [l, r] (1-indexado, inclusivo)
    fn soma_intervalo(&self, l: usize, r: usize) -> i64 {
        if l > r {
            return 0;
        }
        self.prefix_sum(r) - self.prefix_sum(l - 1)
    }

    /// Define o valor na posição pos como novo_valor
    fn definir(&mut self, pos: usize, novo_valor: i64) {
        let valor_atual = self.soma_intervalo(pos, pos); // Valor atual
        let delta = novo_valor - valor_atual;
        self.atualizar(pos, delta);
    }
}

/// Retorna o bit menos significativo: lowbit(x) = x & (-x)
fn lowbit(x: usize) -> usize {
    x & x.wrapping_neg()
}

/// Fenwick Tree bidimensional para consultas de soma em sub-matrizes.
struct FenwickTree2D {
    bit: Vec<Vec<i64>>,
    linhas: usize,
    colunas: usize,
}

impl FenwickTree2D {
    fn novo(linhas: usize, colunas: usize) -> Self {
        FenwickTree2D {
            bit: vec![vec![0; colunas + 1]; linhas + 1],
            linhas,
            colunas,
        }
    }

    /// Atualiza: matriz[lin][col] += delta
    fn atualizar(&mut self, mut lin: usize, col: usize, delta: i64) {
        while lin <= self.linhas {
            let mut c = col;
            while c <= self.colunas {
                self.bit[lin][c] += delta;
                c += lowbit(c);
            }
            lin += lowbit(lin);
        }
    }

    /// Consulta a soma da sub-matriz [1,1] até [lin,col]
    fn prefix_sum(&self, mut lin: usize, col: usize) -> i64 {
        let mut soma: i64 = 0;
        while lin > 0 {
            let mut c = col;
            while c > 0 {
                soma += self.bit[lin][c];
                c -= lowbit(c);
            }
            lin -= lowbit(lin);
        }
        soma
    }

    /// Consulta a soma da sub-matriz [l1,c1] até [l2,c2]
    fn soma_submatriz(&self, l1: usize, c1: usize, l2: usize, c2: usize) -> i64 {
        self.prefix_sum(l2, c2)
            - self.prefix_sum(l1 - 1, c2)
            - self.prefix_sum(l2, c1 - 1)
            + self.prefix_sum(l1 - 1, c1 - 1)
    }
}

/// Fenwick Tree modificada que suporta atualização em intervalo
/// e consulta pontual.
///
/// Truque: armazena as diferenças ao invés dos valores.
/// update(l, r, val): BIT.add(l, val); BIT.add(r+1, -val)
/// query(pos): prefix_sum(pos) = valor em pos
struct FenwickTreeRangeUpdate {
    bit: Vec<i64>,
    n: usize,
}

impl FenwickTreeRangeUpdate {
    fn novo(n: usize) -> Self {
        FenwickTreeRangeUpdate {
            bit: vec![0; n + 2], // +2 para evitar overflow no r+1
            n,
        }
    }

    fn adicionar(&mut self, mut pos: usize, delta: i64) {
        while pos <= self.n {
            self.bit[pos] += delta;
            pos += lowbit(pos);
        }
    }

    /// Soma delta a todos os elementos no intervalo [l, r]
    fn atualizar_intervalo(&mut self, l: usize, r: usize, delta: i64) {
        self.adicionar(l, delta);
        if r + 1 <= self.n {
            self.adicionar(r + 1, -delta);
        }
    }

    /// Consulta o valor na posição pos
    fn consultar(&self, mut pos: usize) -> i64 {
        let mut soma: i64 = 0;
        while pos > 0 {
            soma += self.bit[pos];
            pos -= lowbit(pos);
        }
        soma
    }
}

/// Conta o número de inversões em um array.
/// Uma inversão é um par (i, j) onde i < j mas a[i] > a[j].
/// Complexidade: O(n log n) usando Fenwick Tree.
fn contar_inversoes(arr: &[i32]) -> i64 {
    if arr.is_empty() {
        return 0;
    }

    // Encontra o valor máximo para dimensionar a BIT
    let max_val = *arr.iter().max().unwrap() as usize;
    let mut bit = FenwickTree::novo(max_val + 1);
    let mut inversoes: i64 = 0;

    // Processa da direita para a esquerda
    for &val in arr.iter().rev() {
        let v = val as usize;
        // Conta quantos elementos menores que val já foram inseridos
        // (estão à direita de val no array original)
        if v > 0 {
            inversoes += bit.prefix_sum(v - 1);
        }
        // Registra a presença de val
        bit.atualizar(v, 1);
    }

    inversoes
}

/// Tabela de frequências com consultas de intervalo
struct TabelaFrequencias {
    bit: FenwickTree,
    max_valor: usize,
}

impl TabelaFrequencias {
    fn nova(max_valor: usize) -> Self {
        TabelaFrequencias {
            bit: FenwickTree::novo(max_valor),
            max_valor,
        }
    }

    /// Registra uma ocorrência do valor
    fn registrar(&mut self, valor: usize) {
        assert!(valor >= 1 && valor <= self.max_valor);
        self.bit.atualizar(valor, 1);
    }

    /// Quantos valores no intervalo [l, r] foram registrados?
    fn contar_intervalo(&self, l: usize, r: usize) -> i64 {
        self.bit.soma_intervalo(l, r)
    }

    /// Quantos valores são menores ou iguais a x?
    fn contar_ate(&self, x: usize) -> i64 {
        self.bit.prefix_sum(x)
    }

    /// Total de valores registrados
    fn total(&self) -> i64 {
        self.bit.prefix_sum(self.max_valor)
    }

    /// Encontra o k-ésimo menor valor (busca binária na BIT)
    fn k_esimo(&self, mut k: i64) -> Option<usize> {
        let mut pos = 0;
        let mut bit_mask = 1;

        // Encontra a maior potência de 2 <= max_valor
        while bit_mask <= self.max_valor {
            bit_mask <<= 1;
        }
        bit_mask >>= 1;

        // Busca binária na estrutura da BIT
        while bit_mask > 0 {
            let proximo = pos + bit_mask;
            if proximo <= self.max_valor && self.bit.bit[proximo] < k {
                k -= self.bit.bit[proximo];
                pos = proximo;
            }
            bit_mask >>= 1;
        }

        if pos + 1 <= self.max_valor {
            Some(pos + 1)
        } else {
            None
        }
    }
}

fn main() {
    // === Contagem de Inversões ===
    println!("=== Contagem de Inversões ===\n");

    let arrays = vec![
        vec![2, 4, 1, 3, 5],
        vec![5, 4, 3, 2, 1],
        vec![1, 2, 3, 4, 5],
    ];

    for arr in &arrays {
        let inv = contar_inversoes(arr);
        println!("  {:?} -> {} inversões", arr, inv);
    }

    // === Fenwick Tree Básica ===
    println!("\n=== Fenwick Tree: Vendas Mensais ===\n");

    // Vendas mensais (1 = janeiro, 12 = dezembro)
    let vendas = vec![120, 95, 150, 180, 200, 170, 140, 160, 190, 220, 250, 300];
    let mut bit = FenwickTree::construir(&vendas);

    println!("Vendas acumuladas:");
    println!("  Jan-Mar (Q1): {}", bit.soma_intervalo(1, 3));
    println!("  Abr-Jun (Q2): {}", bit.soma_intervalo(4, 6));
    println!("  Jul-Set (Q3): {}", bit.soma_intervalo(7, 9));
    println!("  Out-Dez (Q4): {}", bit.soma_intervalo(10, 12));
    println!("  Ano total:    {}", bit.prefix_sum(12));

    // Atualização: correção das vendas de março
    println!("\nCorrigindo vendas de março: 150 -> 175");
    bit.atualizar(3, 25); // delta = 175 - 150 = 25
    println!("  Novo Q1: {}", bit.soma_intervalo(1, 3));
    println!("  Novo total: {}", bit.prefix_sum(12));

    // === Tabela de Frequências ===
    println!("\n=== Tabela de Frequências: Notas de Alunos ===\n");

    let mut freq = TabelaFrequencias::nova(10); // Notas de 1 a 10

    // Registra notas dos alunos
    let notas = vec![7, 8, 6, 9, 7, 5, 8, 10, 7, 6, 8, 9, 4, 7, 8];
    for &nota in &notas {
        freq.registrar(nota);
    }

    println!("Distribuição de notas:");
    for nota in 1..=10 {
        let qtd = freq.contar_intervalo(nota, nota);
        let barra = "#".repeat(qtd as usize);
        println!("  Nota {:>2}: {:>2} {}", nota, qtd, barra);
    }

    println!("\nEstatísticas:");
    println!("  Total de alunos: {}", freq.total());
    println!("  Aprovados (nota >= 6): {}", freq.contar_intervalo(6, 10));
    println!("  Reprovados (nota < 6): {}", freq.contar_ate(5));

    // Mediana
    let n = freq.total();
    let mediana_pos = (n + 1) / 2;
    if let Some(mediana) = freq.k_esimo(mediana_pos) {
        println!("  Mediana ({}º valor): {}", mediana_pos, mediana);
    }

    // === Range Update ===
    println!("\n=== Range Update: Bonificação Salarial ===\n");

    // Salários de 8 funcionários (em centenas de R$)
    let n = 8;
    let mut salarios = FenwickTreeRangeUpdate::novo(n);

    // Define salários iniciais
    let iniciais = vec![30, 35, 28, 40, 32, 45, 38, 50];
    for (i, &val) in iniciais.iter().enumerate() {
        salarios.atualizar_intervalo(i + 1, i + 1, val);
    }

    println!("Salários iniciais (x100 R$):");
    for i in 1..=n {
        print!("  [{}]={}", i, salarios.consultar(i));
    }
    println!();

    // Aumento de R$ 500 para funcionários 3 a 6
    println!("\nAumento de R$ 500 para funcionários 3-6:");
    salarios.atualizar_intervalo(3, 6, 5);

    for i in 1..=n {
        print!("  [{}]={}", i, salarios.consultar(i));
    }
    println!();
}

fn processar_operacoes(dados: &[i64], operacoes: &[(&str, usize, i64)]) -> Vec<i64> {
    // Retorna as respostas das consultas Q
    todo!()
}

// Teste:
// dados = [1, 3, 5, 7, 9]
// operações: [("Q", 1, 3), ("U", 2, 10), ("Q", 1, 3)]
// => [9, 16]  (1+3+5=9, depois 1+10+5=16)

fn contar_inversoes_grandes(arr: &[i64]) -> i64 {
    // Dica: ordene os valores únicos e use busca binária
    // para mapear cada valor para sua posição na ordenação
    todo!()
}

// Teste:
// [1000000, 1, 500000, 2] -> 4 inversões

fn soma_submatriz_dinamica(
    n: usize,
    m: usize,
    atualizacoes: &[(usize, usize, i64)],     // (lin, col, valor)
    consultas: &[(usize, usize, usize, usize)] // (l1, c1, l2, c2)
) -> Vec<i64> {
    // Retorna as respostas das consultas
    todo!()
}