Uma Árvore de Índice Binário (Binary Indexed Tree, BIT) ou Árvore de Fenwick é uma estrutura de dados que permite operações eficientes em intervalos. Para um array de tamanho n, a árvore de índice binário suporta as seguintes operações com complexidade de tempo O(log n):

1. Atualização de um único elemento no array, conhecida como atualização pontual (Point Update).
2. Cálculo da soma de elementos em qualquer intervalo do array, conhecida como consulta de intervalo (Range Query).

• Array: A atualização pontual pode ser feita em O(1), mas a consulta de intervalo leva O(n).
• Soma de prefixos: A consulta de intervalo pode ser feita em O(1), mas a atualização pontual requer a atualização de todas as somas de prefixos subseqeuntes, levando a O(n).

Implementação

Operação lowbit

A função lowbit retorna o valor do bit menos significativo de um número.

int lowbit(int i) {
    return i & -i;
}

Estrutura de Dados e Funções Básicas

#include <vector>
using namespace std;

class BIT {
private:
    vector<int> tree;
    int n;

    void add(int index, int value) {
        for (int i = index + 1; i <= n; i += lowbit(i)) {
            tree[i - 1] += value;
        }
    }

    int prefixSum(int index) {
        int res = 0;
        for (int i = index + 1; i > 0; i -= lowbit(i)) {
            res += tree[i - 1];
        }
        return res;
    }

public:
    BIT(vector<int>& nums) {
        n = nums.size();
        tree.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            add(i, nums[i]);
        }
    }

    void update(int index, int value) {
        add(index, value - nums[index]);
        nums[index] = value;
    }

    int rangeSum(int left, int right) {
        return prefixSum(right) - prefixSum(left - 1);
    }
};

Atualização de Intervalo e Consulta Pontual

Para suportar atualizações de intervalo e consultas pontuais, podemos usar a diferença entre os elementos consecutivos.

class RUPQBIT {
private:
    BIT bit;

public:
    RUPQBIT(vector<int>& nums) {
        int n = nums.size();
        vector<int> diffs(n);
        diffs[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            diffs[i] = nums[i] - nums[i - 1];
        }
        bit = BIT(diffs);
    }

    void update(int left, int right, int value) {
        bit.add(left, value);
        bit.add(right + 1, -value);
    }

    int query(int index) {
        return bit.rangeSum(0, index);
    }
};

Atualização de Intervalo e Consulta de Intervalo

Para suportar atualizações de intervalo e consultas de intervalo, precisamos manter duas árvores de índice binário: uma para as diferenças e outra para as somas ponderadas.

class RURQBIT {
private:
    vector<int> diffs, tree, auxTree;
    int n;

    int lowbit(int i) {
        return i & -i;
    }

    void add(vector<int>& t, int index, int value) {
        for (int i = index + 1; i <= n; i += lowbit(i)) {
            t[i - 1] += value;
        }
    }

    int prefixSum(vector<int>& t, int index) {
        int res = 0;
        for (int i = index + 1; i > 0; i -= lowbit(i)) {
            res += t[i - 1];
        }
        return res;
    }

public:
    RURQBIT(vector<int>& nums) {
        n = nums.size();
        diffs.resize(n);
        tree.resize(n);
        auxTree.resize(n);
        diffs[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            diffs[i] = nums[i] - nums[i - 1];
        }
        for (int i = 0; i < n; ++i) {
            add(tree, i, diffs[i]);
            add(auxTree, i, i * diffs[i]);
        }
    }

    void update(int left, int right, int value) {
        add(tree, left, value);
        add(tree, right + 1, -value);
        add(auxTree, left, left * value);
        add(auxTree, right + 1, (right + 1) * (-value));
    }

    int rangeQuery(int left, int right) {
        int preLeft = left * prefixSum(tree, left - 1) - prefixSum(auxTree, left - 1);
        int preRight = (right + 1) * prefixSum(tree, right) - prefixSum(auxTree, right);
        return preRight - preLeft;
    }
};