Estruturas de Dados e Bibliotecas

• Vetores
  • Vetores Estáticos
  • Vetores Dinâmicos
  • Complexidade
  • Ordenação
    • Utilizando o Operador <
    • Utilizando Functores
    • Utilizando Funções
    • Complexidade
  • Busca
    • Complexidade
• Heaps
  • Complexidade
• Pilhas
  • Complexidade
• Filas
  • Complexidade
• Filas de Prioridade
  • Complexidade
• Deques
• Vetores de Bits
  • Bitset
  • Representação através de Vetores Dinâmicos
    • Operações bit-a-bit e máscaras
    • Utilizando Vetores Dinâmicos
    • Complexidade
• Conjuntos
  • Complexidade
• Mapeamentos
  • Complexidade
• Árvores de Segmentos
  • Atualizando Árvores de Segmentos
  • Complexidade
• Árvores de Fenwick
  • Construção da Árvore de Fenwick
  • Realizando Consultas
  • Atualizando Valores
  • Implementação
  • Complexidade
• Leituras Recomendadas

Estruturas de dados proveem meios de organizar e manipular informações de maneira eficiente. Para resolver problemas de uma maneira rápida, fazemos o uso de estruturas de dados adequadas. É papel de um bom programados saber selecionar as melhores estruturas que se encaixam nas soluções propostas. A seguir apresentaremos uma visão sucinta de cada uma delas.

Vetores

Vetores Estáticos

Vetores estáticos correspondem a uma sequência de dados de mesmo tipo. O tamanho deles geralmente é definido na declaração. É possível declarar vetores de uma, duas, três ou até quatro dimensões com facilidade. Quando se sabe de antemão o tamanho máximo de uma entrada, é uma estrutura que pode ser utilizada sem problemas.

Vetores Dinâmicos

É possível projetar vetores que se adequam ao tamanho dos dados. Quando chegam novos dados, o vetor aumenta e quando dados são retirados ele diminui. Felizmente, a maiora das linguagens de alto-nível fornecem estas estruturas em suas bibliotecas padrão. Podemos citar: vector<> (C++) e ArrayList (Java).

Uma série de operações são normalmente disponibilizadas pela API padrão do C++ e podem ser visualizadas neste link.

Através do cabeçalho <vector> é possível utilizar esta estrutura de dados e seus métodos mais notáveis são:

• size: retorna o número de elementos do vetor.
• front: retorna o primeiro elemento do vetor.
• back: retorna o último elemento do vetor.
• operador []: acessa o elemento indexado através da notação de colchetes.
• push_back: insere o elemento x no vetor.
• pop_back: remove o último elemento do vetor.

#include <iostream>
#include <vector>

using namespace std;

template<typename T>
void print_vector(vector<T>& v){
	for(auto value: v){
		cout << value;
	}
	cout << "\n";
}

int main(){
	// declara um vetor sem elementos
	vector<int> empty_vector(); 
	// declara um vetor de 3 posições inicializadas com 1
	vector<int> v(3,1); 
	// declara um vetor contendo os números inteiros de 1 a 5
	vector<int> v2 = {1,2,3,4,5}; 
	// Remove todos os dados do vetor v2
	v2.clear(); 
	// Insere o valor 3 na última posição de v (1,1,1,3);
	v.push_back(3); 
	// Insere o valor 4 na última posição de v (1,1,1,3,4);
	v.push_back(4); 
	// Remove o último elemento de v (1,1,1,3)
	v.pop_back(); 

	// Redimensiona v2 para 10 elementos. 
	v2.resize(10); 

	// Imprime o primeiro elemento do vetor v (1)
	cout << v.front() << "\n"; 
	// Imprime o último elemento do vetor v (3)
	cout << v.back() << "\n" ; 
	// Imprime o terceiro elemento do vetor v (1)
	cout << v[2] << "\n"; 
	// Imprime o tamanho do vetor (4)
	cout << v.size() << "\n"; 

	print_vector(v); // Imprime 1 1 1 3
	print_vector(v2); // O que será impresso?

	return 0;	
}

Note que é possível utilizar a notação padrão de colchetes nesta estrutura.

Complexidade

Ordenação

A STL conta com método de ordenação para o vector chamado de sort.

Caso um tipo nativo da linguagem esteja sendo trabalhado, já existe uma forma padrão de comparação, como ilustrado pelo código abaixo, que ordena em ordem crescente um vetor de strings.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    vector<string> vs = {"Joao","Ariosvaldo","Godofredo","Astrogilda","Hortolina"};
    sort(vs.begin(),vs.end());
    for(auto s: vs){
        cout << s << endl;
    }
    return 0;
}

Caso uma forma não padrão de comparação de elementos seja desejada para obter uma ordenação correta, é possível fazer isso de três formas:

Utilizando o Operador <

Ao implementar o operador < em uma classe, é estabelecida uma relação de ordem entre objetos desta classe, o que pode ser utilizado para ordenação.

No exemplo abaixo, O operador < é definido para estabelecer uma relação de ordem entre duas pessoas. O critério é, uma pessoa deve preceder a outra caso seja mais nova. Se duas pessoas tem a mesma idade, a pessoa com a maior renda mensal precede a outra.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 5;

struct pessoa{
    string nome;   
    int idade; 
    double renda_mensal;
    // O operador < é definido para estabelecer
    // uma ordem entre duas pessoas
    // Critério: primeiro pessoas mais novas e
    // caso tenham a mesma idade, selecionar aquela
    // com maior renda mensal.
    bool operator<(const pessoa& rhs) const{
        if(this->idade < rhs.idade){
            return true;
        }
        if(this->idade == rhs.idade){
            return this->renda_mensal > rhs.renda_mensal;
        }
        return false;
    }
};


void le_pessoa(pessoa& p){
    cout << "Digite o nome: ";
    getline(cin,p.nome);
    cout << "Digite a idade: ";
    cin >> p.idade;
    cout << "Digite a renda mensal em R$: ";
    cin >> p.renda_mensal;
    cin.ignore(1);
}

void imprime_pessoa(pessoa& p){
    cout << p.nome << "\n" << p.idade << "\n"
        << p.renda_mensal << "\n\n";
}
int main(){
    vector<pessoa> v;
    // MAX pessoas são lidas e inseridas em
    // um vetor.
    for(int i=0;i<MAX;i++){
        pessoa p;
        le_pessoa(p);
        v.push_back(p);
    }
    sort(v.begin(),v.end());
    // O vetor é ordenado e as pessoas são impressas.
    for(auto p: v){
        imprime_pessoa(p);
    }
    return 0;
}

Utilizando Functores

Functores são objetos instanciados que permitem ser invocados com funções. Para usar um functor, é necessário criar um operador de função () na classe que descreve o functor. O exemplo da seção anterior adaptado para functores está ilustrado abaixo.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 5;

struct pessoa{
    string nome;   
    int idade; 
    double renda_mensal;
};

struct cmp_pessoa{
    bool operator()(const pessoa& lhs, const pessoa& rhs){
        // O functor estabelece uma ordem entre duas pessoas
        // Critério: primeiro pessoas mais novas e
        // caso tenham a mesma idade, selecionar aquela
        // com maior renda mensal.
        if(lhs.idade < rhs.idade){
            return true;
        }
        if(lhs.idade == rhs.idade){
            return lhs.renda_mensal > rhs.renda_mensal;
        }
        return false;
    }
};


void le_pessoa(pessoa& p){
    cout << "Digite o nome: ";
    getline(cin,p.nome);
    cout << "Digite a idade: ";
    cin >> p.idade;
    cout << "Digite a renda mensal em R$: ";
    cin >> p.renda_mensal;
    cin.ignore(1);
}

void imprime_pessoa(pessoa& p){
    cout << p.nome << "\n" << p.idade << "\n"
        << p.renda_mensal << "\n\n";
}
int main(){
    vector<pessoa> v;
    // MAX pessoas são lidas e inseridas em
    // um vetor.
    for(int i=0;i<MAX;i++){
        pessoa p;
        le_pessoa(p);
        v.push_back(p);
    }
    // Ordenação de acordo com um functor
    sort(v.begin(),v.end(),cmp_pessoa());
    // O vetor é ordenado e as pessoas são impressas.
    for(auto p: v){
        imprime_pessoa(p);
    }
    return 0;
}

Utilizando Funções

Por fim, também é possível indicar qual função de comparação deve ser utilizada no método sort, conforme ilustrado no código abaixo.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX = 5;

struct pessoa{
    string nome;   
    int idade; 
    double renda_mensal;
};

bool cmp_pessoa(const pessoa& lhs, const pessoa& rhs){
    // A função estabelece uma ordem entre duas pessoas
    // Critério: primeiro pessoas mais novas e
    // caso tenham a mesma idade, selecionar aquela
    // com maior renda mensal.
    if(lhs.idade < rhs.idade){
        return true;
    }
    if(lhs.idade == rhs.idade){
        return lhs.renda_mensal > rhs.renda_mensal;
    }
    return false;
}


void le_pessoa(pessoa& p){
    cout << "Digite o nome: ";
    getline(cin,p.nome);
    cout << "Digite a idade: ";
    cin >> p.idade;
    cout << "Digite a renda mensal em R$: ";
    cin >> p.renda_mensal;
    cin.ignore(1);
}

void imprime_pessoa(pessoa& p){
    cout << p.nome << "\n" << p.idade << "\n"
        << p.renda_mensal << "\n\n";
}
int main(){
    vector<pessoa> v;
    // MAX pessoas são lidas e inseridas em
    // um vetor.
    for(int i=0;i<MAX;i++){
        pessoa p;
        le_pessoa(p);
        v.push_back(p);
    }
    // Ordenação de acordo com uma função.
    sort(v.begin(),v.end(),cmp_pessoa);
    // O vetor é ordenado e as pessoas são impressas.
    for(auto p: v){
        imprime_pessoa(p);
    }
    return 0;
}

Complexidade

O método padrão de ordenação da STL leva tempo ótimo $O(n\lg n)$.

Busca

Em vetores ordenados é possível buscar elementos de maneira eficiente do que em uma busca sequencial. Para isto utilizamos dos métodos lower_bound e upper_bound do cabeçalho <algorithm>. Seja $x$ um valor a ser pesquisado, temos:

• lower_bound: retorna um iterador para o primeiro elemento não menor do que $x$.
• upper_bound: retorna um iterador para o primeiro elemento maior do que $x$.

Desta forma, caso $x$ ocorra em um vetor v, temos que de lower_bound até uma posição antes de upper_bound, concentram-se todas as ocorrências de $x$.

O exemplo a seguir de cplusplus ilustra os métodos apresentados.

#include <iostream>     // std::cout
#include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
#include <vector>       // std::vector

int main () {
    int myints[] = {10,20,30,30,20,10,10,20};
    std::vector<int> v(myints,myints+8);           // 10 20 30 30 20 10 10 20

    std::sort (v.begin(), v.end());                // 10 10 10 20 20 20 30 30

    std::vector<int>::iterator low,up;
    low=std::lower_bound (v.begin(), v.end(), 20); //          ^
    up= std::upper_bound (v.begin(), v.end(), 20); //                   ^

    std::cout << "lower_bound at position " << (low- v.begin()) << '\n';
    std::cout << "upper_bound at position " << (up - v.begin()) << '\n';

    return 0;
}

Complexidade

Internamente estes procedimentos realizam uma busca binária. Por esta razão, tanto lower_bound quanto upper_bound levam tempo $O(\lg n)$.

Heaps

Uma Heap é uma estrutura de dados em forma de árvore binária completa que possui a seguinte propriedade:

• A raiz tem precedência sobre os seus dois filhos.
• A árvore com raiz no filho da esquerda é uma heap.
• A árvore com raiz no filho da direita é uma heap.

A figura a seguir ilustra uma Heap.

Como se trata de uma árvore binária completa, é possível representar uma Heap através de um vetor. A navegação desta árvore virtual através de uma aritmética simples. Se um nó ocupa o índice $i$ do vetor, temos:

• O pai ocupa a posição $(i-1)/2$.
• O filho da esquerda ocupa a posição $(i*2) +1$.
• O filho da direita ocupa a posição $(i*2) + 2$.

Usando esta representação, é possível representar a árvore anterior pelo seguinte vetor:

A grande vantagem de uma heap é que o elemento de maior precedência encontra-se na raiz da árvore, ou seja, na posição $0$ do vetor. Assim, dado que um vetor tenha a propiedade de heap, é possível encontrar o elemento de maior precedência em tempo $O(1)$.

Para remover o elemento de maior precedência, trocamos ele com a última folha e, partindo da raiz, trocamos com o maior dos seus filhos até que isto não seja mais possível. Isso é exemplificado pelos seguintes códigos:

template<typename T>
void heapify_top_down(vector<T>& v,size_t idx,size_t heap_size){
    while(idx < heap_size){
 
        // Seleciona os índices dos filhos da direita e da esquerda
        size_t l = 2*idx+1;
        size_t r = 2*idx+2; 

        size_t largest = idx;

        // Verifica se o filho da esquerda existe e ele
        // é maior que o pai
        if(l<heap_size && v[l] > v[largest]){
            // O filho da esquerda é considerado o maior
            largest = l;            
        }
        // Verifica se o filho da direita existe e ele é maior
        // do que o maior até o momento 
        if(r<heap_size && v[r]>v[largest]){
            largest = r;
        }

        if(idx == largest){
            // se o maior continua sendo o pai, paramos.
            break;
        }

        // Trocamos o pai com o maior dos filhos
        swap(v[idx],v[largest]);
        // Atualizamos o valor de idx para continuar o processo
        idx = largest;
    }
}

template<typename T>
void heap_remove(vector<T>& v){
    // trocamos o elemento da raiz pela última folha
    swap(v.front(),v.back());
    // Aplicamos heapify_top_down a partir da raiz
    //desconsiderando o último elemento, que será removido
    heapify_top_down(v,0,v.size()-1);
    // Removemos o último elemento
    v.pop_back();
}

Para inserir o processo inverso é feito: o novo elemento é adicionado no final do vetor como uma folha e ele é trocado com o pai até que ele atinja a posição $0$ (raiz) ou até que ele tenha menor precedência que o seu pai, conforme ilustrado pelos códigos a seguir.

template<typename T>
void heapify_bottom_up(vector<T>& v,size_t idx){
    // Enquanto não chegarmos na raiz
    while(idx!=0){
        // Verifica se o elemento inserido é maior do que o pai
        // Em caso verdadeiro, troque com o pai e continue o procedimento
        size_t parent = (idx-1)/2;
        if(v[parent]<v[idx]){
            // Trocamos o elemento recém inserido pelo seu pai e continuamos
            // o processo
            swap(v[parent],v[idx]);
            idx = parent;
        }
        else{
            break;
        }
    }
}

template<typename T>
void heap_insert(vector<T>& v, T& value){
    // Inserimos o novo elemento como uma folha da heap
    v.push_back(value);
    // Aplicamos Heapify de baixo para cima a partir da folha
    heapify_bottom_up(v,v.size()-1);
}

Para transformar um vetor em uma heap, para que as operações supracitadas possam ser aplicadas, podemos simplesmente examinar os elementos, em ordem decrescente de altura, aplicando o procedimento de trocá-los com os seus filhos sempre que tiverem menor precedência, como abaixo:

template<typename T>

void make_heap(vector<T>& v){
    for(int64_t i = v.size()/2; i>=0;i--){
        heapify_top_down(v,i,v.size());
    }
}

É possível utilizar esta estrutura de dados através do cabeçalho <algorithm>. Os métodos mais notáveis são:

• make_heap: transforma um vetor em uma Heap.
• front: retorna o elemento de maior precedência de uma Heap.
• pop_heap: reestrutura a Heap para remover o elemento de maior precedência. Deve ser acompanhado de um pop_back
• push_heap: reestrutura a Heap após a inserção de um elemento. Deve ser precedido de um push_back.

O seguinte código ilustra a operação de uma Heap.

#include <iostream>      
#include <algorithm>     
#include <vector>       

using namespace std;

int main () {
    vector<int> v = {10,20,30,5,15};

    // Constrói a Heap a partir do vetor
    make_heap(v.begin(),v.end());
    std::cout << "Elemento de maior precedência   : " << v.front() << '\n';

    // Reestrutura a heap para remover o elemento de maior precedência
    std::pop_heap (v.begin(),v.end());
    // Remove o elemento de maior precedência
    v.pop_back();
    std::cout << "Elemento de maior precedência: " << v.front() << '\n';

    // Insere um elemento no fim do vetor e reestrutura a Heap
    v.push_back(99);
    std::push_heap (v.begin(),v.end());
    std::cout << "Maior elemento após inserção: " << v.front() << '\n';

    return 0;
}

Complexidade

Como virtualmente temos uma árvore completa e cheia, as operações de inserção de um elemento e remoção do elemento de maior precedência levam tempo proporcional a altura da árvore, que é no máximo $O(\lg n)$.

O acesso ao elemento de maior precedência leva tempo constante: basta acessar a posição $0$ do vetor.

Pilhas

Pilhas são estruturas de dados que seguem a ordem LIFO (Last-in-first-out), ou seja, os últimos elementos que entram, são os primeiros a serem retirados.

Esta estrutura está disponível através do cabeçalho <stack> e seus métodos mais notáveis são:

• top: retorna o elemento que ocupa o topo da pilha.
• push: insere um elemento na pilha.
• pop: retira um elemento da pilha.
• empty: verifica se a pilha está vazia.
• size: retorna o tamanho da pilha.

O exemplo a seguir utiliza uma pilha para ler uma série de nomes e imprimí-los em sua ordem inversa.

#include <iostream>
#include <stack>

using namespace std;

const int MAX = 5;

int main(){
    // Pilha vazia de strings
    stack<string> stck;
    // Lê MAX nomes e os coloca em uma pilha
    for(int i=0;i<MAX;i++){
        string s;
        getline(cin,s);
        stck.push(s);
    }
    // Enquanto a pilha não está vazia
    // imprima o topo da pilha
    // e remova o elemento do topo 
    while(!stck.empty()){
        cout << stck.top() << endl;
        stck.pop();
    }
    return 0;	
}

Complexidade

Filas

Ao contrário das Pilhas, Filas são estruturas de dados que seguem a ordem FIFO (first-in-first-out), ou seja, o primeiro elemento que é inserido, deve ser o primeiro a retirado.

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 5;

int main(){
    // Fila vazia de strings
    queue<string> q;
    // Lê MAX nomes e os coloca em uma fila
    for(int i=0;i<MAX;i++){
        string s;
        getline(cin,s);
        q.push(s);
    }

    // Enquanto a fila não está vazia,
    // imprima a frente da fila
    // e remova o elemento da frente. 
    while(!q.empty()){
        cout << q.front() << endl;
        q.pop();
    }
    return 0;	
}

Complexidade

Filas de Prioridade

Filas de prioridade não seguem a ordem FIFO. Elas procuram estabelecer uma prioridade entre os elementos de forma que, independentemente de quando foi inserido, o elemento de maior prioridade deve ser retirado.

Internamente, esta estrutura de dados geralmente é implementada através de uma Heap e está disponível através do cabeçalho <queue>. Podemos citar como exemplos os métodos:

• empty: verifica se a fila de prioridade está vazia;
• size: retorna o tamanho da fila de prioridade;
• top: retorna o elemento de maior prioridade;
• push: insere um elemento na fila de prioridade;
• pop: remove o elemento de maior prioridade.

O código abaixo mostra uma situação hipotética em que várias pessoas são inseridas em uma fila de prioridade. Neste caso, definimos através do operador < uma relação de ordem entre as pessoas para que duas pessoas possam ser comparadas e avaliadas de acordo com a sua prioridade. No caso, pessoas mais velhas tem mais prioridade do que pessoas mais novas e que, quando as pessoas tem a mesma idade, a com menor renda mensal tem prioridade.

#include <iostream>
#include <queue>

using namespace std;

const int MAX = 5;

struct pessoa{
    string nome;   
    int idade; 
    double renda_mensal;
    // O operador < é definido para estabelecer
    // prioridade entre duas pessoas
    // Critério: primeiro pessoas mais velhas e
    // caso tenham a mesma idade, selecionar aquela
    // com menor renda mensal.
    bool operator<(const pessoa& rhs) const{
        if(this->idade < rhs.idade){
            return true;
        }
        if(this->idade == rhs.idade){
            return this->renda_mensal > rhs.renda_mensal;
        }
        return false;
    }
};


void le_pessoa(pessoa& p){
    cout << "Digite o nome: ";
    getline(cin,p.nome);
    cout << "Digite a idade: ";
    cin >> p.idade;
    cout << "Digite a renda mensal em R$: ";
    cin >> p.renda_mensal;
    cin.ignore(1);
}

void imprime_pessoa(pessoa& p){
    cout << p.nome << "\n" << p.idade << "\n"
        << p.renda_mensal << "\n\n";
}
int main(){
    priority_queue<pessoa> pq;
    // MAX pessoas são lidas e inseridas em
    // uma fila de prioridade.
    for(int i=0;i<MAX;i++){
        pessoa p;
        le_pessoa(p);
        pq.push(p);
    }
    // As pessoas são retiradas da fila de prioridade
    // com base na ordem estabelecida pelo operador <
    while(!pq.empty()){
        pessoa p = pq.top();
        imprime_pessoa(p);
        pq.pop();
    }
    return 0;
}

Considere a seguinte entrada:

O programa selecionaria as seguintes pessoas de acordo com a prioridade pré-definida:

Pablo
80
6000

Jose
50
2000

Daniela
30
400

Carlos
30
500

Daniel
20
1000

Complexidade

Como são baseadas em Heaps, as filas de prioridade possuem as seguintes complexidades.

Deques

Deques (Double-ended queues), são estruturas de dados que combinam pilhas e filhas. É possível inserir e remove elementos das duas extremidades e normalmente utiliza-se uma estrutura híbrida de vetor e listas na implementação.

Os deques podem ser utilizados através do cabeçalho <queue> e os principais métodos podem ser elencados como:

• front: acessa o elemento que está na cabeça do deque.
• back: acessa o elemento que está na cauda do deque.
• push_back: inserção na cauda do deque.
• pop_back: remoção na cauda do deque.
• push_front: inserção na cabeça do deque.
• pop_front: remoção na cabeça do deque.
• empty: verifica se o deque está vazio.
• size: retorna o tamanho do deque.
• Operador []: retorna o elemento do deque na posição indicada na notação de colchetes.

Vetores de Bits

Vetores de bits são estruturas que representam uma sequência de valores $0$ ou $1$. Em comparação com um vetor, essas estruturas são preferidas neste cenário pois conseguem economizar espaço e tempo, uma vez que menos acessos a memória são feitos para recuperar valores.

Bitset

O C++ oferece através da STL a classe bitset, que permite a criação de vetores de bits estáticos. Ou seja, o tamanho da estrutura deve ser definida em tempo de compilação e não pode ser redimensionada.

Esta classe possibilita:

• set: atribui ao bit indicado o valor $1$.
• reset: atribui ao bit indicado o valor $0$
• flip: inverte o bit de uma determinada posição.
• count: conta o números de bits com valor $1$.
• operador []: acessa o bit indexado pela notação de colchetes.

O código a seguir exemplifica o uso dessa estrutura.

#include <iostream>
#include <bitset>

using namespace std;

int main(){
    // Criação de uma sequência estática de 10 bits
    bitset<10> b;
    // Ligamos os bits 0, 5 e 7
    b.set(0);
    b.set(5);
    b.set(7);

    for(size_t i=0;i<b.size();i++){
        cout << "Valor do bit " << i << ": " << b[i] << "\n";
    }
    return 0;
}

Representação através de Vetores Dinâmicos

Operações bit-a-bit e máscaras

Podemos representar os vetores de bits através de um vetor de inteiros, basta lembrar que qualquer inteiro é representado por uma sequência de bits.

Por exemplo, o inteiro

42 (decimal) = 101010 (binário)

Para acessar o valor de um bit em específico, usamos os operadores bit-a-bit em conjunção com as máscaras de bit.

Estes operadores aplicam uma operação lógica em um inteiro, no caso de um operador unário, ou entre dois inteiros, no caso de um operador binário.

• Operador unário: ~ (NOT).
• Operadores binários: & (AND), | (OR), ^ (XOR), << (Shift-left) e >> (Shift-right).

Os operadores de >> e << servem para deslocar os bits posições à esquerda ou a direita.

Por exemplo: 00101010 >> 1 = 00010101 (binário) = 21 (decimal) e 00101010 << 2 = 10101000 (binário) = 168 (decimal).

Efetivamente, deslocar $i$ posições à esquerda significa realizar a uma multiplicação por $2^i$. Ao deslocar $i$ posições à direita, o resultado equivale a uma divisão inteira por $2^i$.

Considerando o inteiro de 8 bits x = 42 (decimal) = 00101010 (binário), ao aplicar o operador ~ sobre ele, teríamos:

~x = 11010101 = 213 (decimal sem sinal) = -43 (decimal com sinal)

Ou seja, este operador flipa todos os bits de um inteiro.

Tomando agora como exemplo os inteiros de 8 bits x = 42 (decimal) = 00101010 (binário) e y = 195 (decimal) = 11000011 obteríamos o seguinte ao aplicar os operadores &, | e ^ entre eles:

  00101010       00101010       00101010
  11000011       11000011       11000011
& --------     | --------     ^ --------
  00000010       11101011       11101001

Ou seja, respectivamente as operações de AND, OR e XOR bit-a-bit.

Através desses operadores, podemos ligar, desligar, inverter e checar o valor de um bit em específico utilizando as máscaras de bit.

Para ligar o i-ésimo bit (base $0$) de um inteiro x, usamos o operador | aplicado com a máscara 1 << i. Por exemplo, se x=42 (decimal) = 00101010 e desejamos ligar o bit 7, basta operar 00101010 com 1 << 7 = 10000000.

  00101010
  10000000
| --------
  10101010

Para resetar o i-ésimo bit, fazemos uma operação análoga, mas dessa vez utilizando a máscara ~(1<<i), que deixa todos os bits ligados, com exceção do i-ésimo, em conjunção com o operador &.

Caso quiséssemos desligar o bit $1$ do número x=00101010, teríamos:

  00101010
  11111101
& --------
  00101000 

Para alternar o valor do i-ésimo bit, utilizamos a máscara (1<<i) aplicada com o operador ^. Considerando o inteiro x = 00101010 (binário) e o bit $2$, teríamos:

  00101010
  00000100
^ --------
  00101110 

Para checar o valor do i-ésimo bit, basta utilizar a máscara (1<<i) em conjunção com o operador &. Se o resultado for diferente de $0$, então o i-ésimo bit está ligado, caso contrário, desligado. Considerando o inteiro x = 00101010 (binário) e o bit $3$, temos:

  00101010
  00001000
& --------
  00001000 

Como 00001000 = 8 (decimal) é diferente de zero, sabemos que o bit $3$ está ligado.

Repetindo a mesma consulta para o bit $4$, teríamos:

  00101010
  00010000
& --------
  00000000 

Portanto, conseguimos concluir que o bit $4$ está desligado.

Utilizando Vetores Dinâmicos

Vimos como manipular bits utilizando inteiros, no entanto, utilizando apenas um inteiro, só conseguimos manipular uma quantidade de bits comportada por este inteiro. Para representar uma sequência maior de bits, podemos utilizar um vetor de inteiros.

Considerando um vetor de inteiros de $64$-bits v, temos que v[0] armazena os bits $0$ a $63$, v[1] os bits $64$ a $127$ e v[i] os bits i*64 a (i+1)*64 - 1.

Assim, caso seja desejado manipular o $k$-ésimo bit desta sequência precisamos responder duas questões:

• Em que inteiro esse bit se encontra?
• Dentro deste inteiro, qual o índice deste bit?

Como se trata de um vetor de inteiros de $64$-bits, a primeira questão pode ser respondida através da divisão inteira por $64$. Assim, sabemos que o bit que desejamos manipular está na posição v[k/64] ou equivalentemente v[k>>6], se desejamos evitar uma divisão.

Agora que sabemos que o bit desejado se encontra no inteiro v[k>>6], como localizar o índice deste bit neste inteiro? Simples, pegando o resto da divisão de $k$ por $64$. Logo o índice do bit desejado no inteiro é k % 64 ou k & (63).

Conhecendo o inteiro que contém o bit e o índice deste bit no inteiro, podemos manipular o bit conforme apresentado anteriormente.

Sumarizando o discutido, o código a seguir exemplifica como manipular os bits dentro de um vetor de inteiros.

#include <cstdint>
#include <vector>

using namespace std;

/**
 * @brief Liga o k-ésimo bit do vetor 
 * @param v: vetor de bits
 * @param k: o bit a ser ligado
 */
void set_bit(vector<uint64_t>& v,size_t k){
    v[k>>6] |= (1ULL << (k & (63)));
}

/**
 * @brief Desliga o k-ésimo bit do vetor 
 * @param v: vetor de bits
 * @param k: o bit a ser ligado
 */
void reset_bit(vector<uint64_t>& v,size_t k){
    v[k>>6] &= ~(1ULL << (k & (63)));
}

/**
 * @brief Alterna o k-ésimo bit do vetor 
 * @param v: vetor de bits
 * @param k: o bit a ser ligado
 */
void flip_bit(vector<uint64_t>& v,size_t k){
    v[k>>6] ^= 1ULL << (k & (63));
}

/**
 * @brief Consulta o k-ésimo bit do vetor 
 * 
 * @param v: vetor de bots
 * @param k: o bit a ser desligado 
 * @return true caso o k-ésimo bit seja 1
 * @return false caso o k-ésimo bit seja 0
 */
bool query_bit(vector<uint64_t>& v,size_t k){
    return v[k>>6] & (1ULL << (k & (63)));
}

Complexidade

Todas as operações em vetores de bits levam tempo $O(1)$, uma vez que qualquer operação exige um número fixo de expressões aritméticas e atribuições.

Conjuntos

O tipo de dados abstrato conjunto estabelece uma coleção de elementos distintos. Nele é possível através de uma chave: inserir elementos; remover elementos; buscar elementos.

A STL do C++ disponibiliza a classe set que implementa este tipo abstrato de dados cujos métodos mais relevantes são:

• insert: insere um dado elemento no conjunto.
• erase: remove um dado elemento do conjunto.
• find: busca um dado elemento no conjunto.

A implementação de um conjunto normalmente é feito através de árvores binárias balanceadas, normalmente Red-Black Trees no caso da STL, isso configura tempos de inserção, remoção e busca competitivos na prática. Por conta desta representação, é possível recuperar todos os elementos do conjunto de forma ordenada usando os iteradores.

O código a seguir ilustra a utilização de um conjunto para inserção/remoção/busca de nomes lidos pelo o usuário. Assim que um nome já inserido consta no conjunto, uma mensagem é apresentada. Se o usuário tenta apagar um nome não existente, também recebe um alerta. No final da execução de tal código, todos os nomes são impressos de acordo com a ordem lexicográfica.

#include <iostream>
#include <set>

using namespace std;

int main(){
    set<string> s;
    for(int opt=1;opt!=4;){
        string name;
        cout << "Opção 1: Inserir nome." << endl;
        cout << "Opção 2: Remover nome." << endl;
        cout << "Opção 3: Buscar nome." << endl;
        cout << "Opção 4: sair." << endl;
        cout << "\nDigite a opção: ";
        cin >> opt;
        cin.ignore(1); //Pula caractere de quebra de linha
        if(opt==1){
            cout << "Digite um nome a ser inserido: ";
            getline(cin,name);
            // Insere o nome e captura o retorno.
            // Caso o elemento já conste no conjunto
            // o segundo membro do par é falso.
            auto rv = s.insert(name);
            if(!rv.second){
                cout << "Nome já inserido, ignorando.\n";
            }
        }
        else if(opt==2){
            cout << "Digite o nome a ser removido: ";
            getline(cin,name);
            // Erase retorna o número de elementos apagados com sucesso
            auto rv = s.erase(name);
            if(rv>0){
                cout << name << " apagado com sucesso.\n";
            }
            else{
                cout << "Nome não constava no conjunto.\n";
            }
        }
        else if(opt==3){
            cout << "Digite o nome a ser buscado: ";
            getline(cin,name);
            if(s.find(name) != s.end()){
                cout << name << " consta no conjunto.\n";
            }
            else{
                cout << name << " não consta no conjunto.\n";
            }
        }
        else if(opt!=4) {
            cout << "Opção não reconhecida.";
        }
    }
    cout << "Imprimindo nomes em ordem lexicográfica\n";
    for(auto value: s){
        cout << value << endl;
    }
    return 0;
}

Complexidade

Por serem implementados através de árvores balanceadas, os conjuntos possuem tempo $O(\lg n)$ para as suas operações mais notáveis, uma vez que é este o tempo envolvido de pior caso em um percurso que vai da raiz até uma folha.

Mapeamentos

O mapeamento é um TAD que associa uma chave a um valor, assim como em uma função matemática, em que um conjunto é associado a outro.

Uma implementação desta abstração é fornecida pelo cabeçalho <map> da STL. Um mapeamento que mapeia uma chave do tipo A em um valor do tipo B, pode ser declarado como map<A,B> nome_variavel. Assim como os conjuntos, o mapeamento é implementado através de Red-Black Trees.

Os métodos mais notáveis de um map podem ser elencados como:

• insert: insere um par chave-valor em um mapeamento.
• erase: apaga um par chave-valor de acordo com a chave.
• find: consulta um determinado par chave-valor a partir de uma chave.
• operador []: permite inserir e recuperar um par chave-valor do mapeamento.

O exemplo abaixo ilustra como realizar a inserção e consulta em um mapeamento através do operador []. O map em questão trata-se de um mapeamento do tipo string para o tipo double. No caso do programa, a cada nome de fruta é associado o preço por Kg daquela fruta.

#include <iostream>
#include <iomanip> // setprecision
#include <map>

using namespace std;

int main(){
    map<string,double> m;
    m["banana"] = 3.14;
    m["maca"] = 9.28;
    m["limao"] = 1.72;

    // Se comprarmos 2 quilos de banana, um quilo e meio de maçã
    // e 5 quilos de limão, esse seria o resultado;
    double total = 2*m["banana"] + 1.5*m["maca"] + 5*m["limao"];
    cout << "Total sacolão: " << fixed << setprecision(2) << total << endl;
    return 0;
}

O map também armazena os valores em ordem crescente pela chave, então é possível recuperar os valores de acordo com essa ordem como feito no set.

Existem algumas nuances em relação à inserção e ao operador [] que podem ser conferidas com mais detalhe aqui

Complexidade

Por serem implementados através de árvores balanceadas, os conjuntos possuem tempo $O(\lg n)$ para as suas operações mais notáveis, uma vez que é este o tempo envolvido de pior caso em um percurso que vai da raiz até uma folha.

Árvores de Segmentos

Árvores de Segmentos são extremamente úteis para realizar consultas sobre intervalos de um vetor. Por exemplo, tome o problema do Range Minimum Query (RMQ), que dado um intervalo [i,j] de um vetor v, consiste em achar o índice $i \leq k \leq j$ de v tal que v[k] seja o menor possível considerando este intervalo. Para um vetor v com os valores 19 17 12 20 16 12 21, $RMQ(1,3)$, retornaria o índice $2$, uma vez que dentre v[1], v[2] e v[3], v[2] = 12 é aquele que possui o menor valor no intervalo considerado.

Claramente o problema do RMQ pode ser resolvido com uma busca simples em tempo $O(m)$, onde $m$ é o tamanho do intervalo considerado. No entanto, é possível fazer melhor com as árvores de segmentos e reduzir essa complexidade para $O(\lg n)$, em que $n$ é o tamanho do vetor.

Uma árvore de segmentos para o problema do RMQ é uma árvore binária balanceada e completa em que cada nó representa um intervalo que armazena a resposta da consulta. As propriedades desta árvore de segmentos podem ser detalhadas como:

• A raiz representa o intervalo $[0,n-1]$ e armazena a resposta de $RMQ(0,n-1)$.
• Cada folha representa um intervalo unitário $[k,k]$ e armazena a resposta de $RMQ(k,k) = k$.
• Cada nó interno representa um intervalo $[i,j]$ e armazena a resposta de $RMQ(i,j)$. Este segmento do nó interno pode ser dividido em dois sub-segmentos: $[i,(i+j)/2]$ e $[(i+j)/2 + 1,j]$ que dão origem respectivamente aos filhos da esquerda e direita do nó interno original.

A figura a seguir sumariza o descrito até o momento para o vetor com os valores 19 17 12 20 16 12 21.

Para responder uma consulta $RMQ(i,j)$ utilizamos o seguinte raciocínio recursivo:

• Se o nó representa um intervalo fora da faixa $[i,j]$, retorne $\bot$ (indefinição).
• Se o intervalo do nó está contido em $[i,j]$, retorne o índice armazenado pelo nó.
• Caso contrário, o intervalo representado pelo nó não está contido no intervalo da consulta. Assim, tomamos recursivamente $a = RMQ(i,(i+j)/2)$, o que pode ser obtido pelo filho da esquerda e $b = RMQ((i+j)/2 +1,j)$, o que pode ser obtido pelo filho da direita. Se $a$ e $b$ estão indefinidos, retorne $\bot$. Se $a$ e $b$ não estão indefinidos, retorne $v[a]\leq v[b]$ e $b$ caso contrário. Senão, retorne o valor que não está indefinido.

Por exemplo, tomando a consulta $RMQ(1,4)$ em questão, a busca inciaria da raiz da árvore que representa o intervalo $[0,6]$, como o intervalo do nó não está contido no intervalo da consulta, procedemos recursivamente para o filho da esquerda e o filho da direita.

• O filho da esquerda, que representa o intervalo $[0,3]$, ainda não está contido em $[1,4]$, procedemos para os nós com intervalos $[0,1]$ e $[2,3]$. A consulta sobre o nó $[0,1]$ é dividida em duas, que retornam $\bot$ e $1$. Já o nó $[2,3]$ está contido em $[1,4]$, assim a consulta deste filho retorna $2$. Por fim, dentre os resultados da consulta sobre $a = RMQ(1,1)$ e $b =RMQ(2,3)$, selecionamos $b$, pois $v[a] \leq v[b]$.
• O filho da direita representa o intervalo $[4,6]$, que não está contido em $[1,4]$. Dividimos a consulta em duas sobre os filhos da esquerda ($[4,5]$) e o filho da direita ($[6,6]$). O intervalo $[4,5]$ ainda não está contido em $[4,4]$, assim, a consulta é dividida entre $[4,4]$ e $[5,5]$, que retornam $4$ e $\bot$ respectivamente. A consulta sobre o intervalo $[6,6]$ retornará $\bot$. Por fim, dentre os resultados das consultas sobre $[4,4]$ e $[6,6]$, escolhemos a primeira, pois está definida.

Com tudo o que foi discutido, podemos implementar a árvore de segmentos da seguinte maneira (Halim & Halim).

#include <iostream>
#include <vector>

using namespace std;

class segment_tree{
private:
    // Vetor da árvore de segmentos
    vector<int> st;
    // Cópia do vetor original
    vector<int>& v;
    // size of v
    int n;

public:
    /**
     * @brief Constrói um objeto do tipo Árvore de Segmentos
     * 
     * @param vec vetor original 
     */
    segment_tree(const vector<int>& vec):v(vec){
        n = vec.size();
        // Aloca espaço para a árvore de segmentos
        st = vector<int>(4*n,0);
        // Constrói a partir da raiz (índice 1) e do intervalo [0,n-1]
        build(1,0,n-1);
    }
    /**
     * @brief Sobrecarga de rmq, deixa a chamada de função mais limpa
     * 
     * @param i limite inferior do intervalo da consulta.
     * @param j limite superior do intervalo da consulta
     * @return int RMQ(i,j)
     */
    int rmq(int i,int j){
        // Simplesmente chama a versão completa de rmq
        return rmq(1,0,n-1,i,j);
    }

private:
    /**
     * @brief Retorna o índice do filho da direita.
     * 
     * @param p índice do pai
     * @return int índice do filho da direita.
     */
    int left(int p){
        return p << 1;
    }
    /**
     * @brief Retorna o índice do filho da esquerda.
     * 
     * @param p índice do pai.
     * @return int índice do filho da direita.
     */
    int right(int p){
        return (p << 1) + 1;
    }
    /**
     * @brief Contrói a árvore de segmentos st
     * 
     * @param p índice do pai
     * @param i limite inferior do intervalo do nó p
     * @param j limite superior do intervalo do nó p
     */
    void build(int p,int i,int j){
        /***
         * Caso base: o nó com índice p corresponde a uma folha, então
         * st[p] = i
         ***/
        if(i==j){
            st[p] = i;
        }
        /***
         * Caso geral. O nó não é uma folha. Calculamos recursivamente as
         * respostas dos filhos da esquerda e da direita para poder calcular
         * a resposta nó com índice p
         ***/
        else{
            build(left(p),i,(i+j)/2);
            build(right(p),(i+j)/2 + 1,j);
            int a = st[left(p)];
            int b = st[right(p)];
            /***
             * Seja a a resposta do filho a esquerda e b a do filho da direita.
             * Pegamos o índice cujo valor é o menor e armazenamos em st[p].
             ***/
            st[p] = (v[a] <= v[b]) ? a : b;
        }
    }
    /**
     * @brief Executa a consulta de rmq
     * 
     * @param p índice do nó na árvore de segmentos
     * @param l limite inferior do intervalo do nó
     * @param r limite superior do intervalo do nó
     * @param i limite inferior do intervalo da consulta
     * @param j limite superior do intervalo da consulta
     * @return int RMQ(i,j)
     */
    int rmq(int p,int l,int r,int i,int j){
        // Se [l,r] é disjunto de [i,j] retorna indefinição
        if(i>r || j<l) return -1;
        // Se [l,r] está contido em [i,j], retorne st[p] = RMQ(l,r)
        if(l>=i && r<=j) return st[p];
        /***
         * Senão, obtenha recursivamente as respostas nos filhos da esquerda 
         * e direita e selecione a resposta que minimiza o valor do intervalo
         * [i,j]
         */
        int a = rmq(left(p),l,(l+r)/2,i,j);
        int b = rmq(right(p),(l+r)/2 + 1,r,i,j);
        if(a == -1) return b;
        if(b == -1) return a;
        return(v[a] <= v[b]) ? a : b;
    }
};


int main(){
    vector<int> v = {19,17,12,20,16,12,21};
    segment_tree segtree(v);
    cout << "RMQ(1,4) = " << segtree.rmq(1,4) << endl;
    return 0;
}

Pode ser observado que a função build computa, de baixo para cima, os valores de cada nó da árvore de segmentos, enquanto a função rmq faz exatamente o descrito anteriormente no procedimento de consulta de $RMQ(i,j)$.

Atualizando Árvores de Segmentos

As árvores de segmentos permitem a utilização de consultas de RMQ em um cenário dinâmico, isto é, em que os valores mudam. Por exemplo, se o valor de v[i] é modificado, apenas é necessário recomputar as respostas do caminho da raiz até a folha com intervalo $[5,5]$ em tempo proporcional a altura da árvore $O(\lg n)$.

Complexidade

Por se tratar de uma árvore balanceada, todas as operações que envolvem uma árvore de segmentos e percorrem de uma raiz até a folha, levam tempo $O(\lg n)$, o que é muito melhor do que uma busca linear, que leva tempo $O(n)$.

Árvores de Fenwick

As árvores de Fenwick foram propostas por Peter Fenwick na década de 90 e são muito utilizadas no problema de cálculo de frequências cumulativas em um cenário dinâmico, que dado um vetor v (com base em $1$) e um intervalo [1,i], consiste em determinar a soma dos valores v[k] $1 \leq k \leq i$, também denotado por $sum(i)$. Uma variação deste problema, consiste em determinar a soma de um intervalo $[i,j]$, denotada por $sum(i,j)$. Cabe ressaltar que os valores de v podem ser alterados no decorrer do tempo, alterando o resultado da soma cumulativa.

Claramente, consultas de $sum$ podem ser resolvidas com uma inspeção linear no intervalo, contudo, ela teria complexidade linear no tamanho do intervalo e, dependendo do número de consultas, isso seria inviável.

Uma possível solução para resolver este problema é adaptar as Árvores de Segmentos vistas anteriormente, contudo, as Árvores de Fenwick são consideradas estruturas mais simples e fáceis de implementar.

Tomando a abordagem presente em (Topcoder), considere um vetor v indexado em $1$. A ideia por trás de uma Fenwick Tree é representá-la através de um vetor ft de tal forma que ft[i] armazena a soma acumulada de v no intervalo $[i-2^{lsb(i)}+1,i]$ em que $lsb(i)$ corresponde ao índice do bit $1$ menos significativo de $v[i]$. A Tabela a seguir ilustra isso, em que v é o vetor original, c é a frequência cumulativa e ft é a árvore de fenwick.

Já a Tabela seguinte ilustra o intervalo considerado por cada nó da ft.

A árvore ft pode ser ilustrada da seguinte forma:

Construção da Árvore de Fenwick

Para construir o vetor ft em tempo $O(n)$, primeiramente transformamos o vetor v no vetor de soma cumulativa c.

f = vector<int>(v.size());
f[0] = 0;
for(size_t i=1;i<v.size();i++){
    f[i] = f[i-1]+c[i];
}

Com posse disso, basta notar que qualquer soma sobre um intervalo $[i,j]$ pode ser decomposta em uma subtração a partir de $c$. Como $c[j]$ contém a soma de $[1,j]$ e $c[i-1]$ contém a soma de $[1,i-1$], concluímos que a soma do intervalo $[i,j]$ é obtida por $c[j]-c[i-1]$.

Logo, qualquer árvore de Fenwick pode ser construída em tempo $O(n)$.

Realizando Consultas

Para realizar uma consulta de $sum(i)$, precisamos abranger todos os nós que cobrem inteiramente o intervalo $[1,i]$. Tomando $i=7$ e o nosso exemlo anterior, temos que a $sum(7)$ = $sum(111b)$ = ft[111b] + ft[110b] + ft[100b] = $18$. Ou seja, o índice do próximo nó a ser somado consiste do índice anterior com o bit $1$ menos significativo desligado. Este procedimento equivale a fazer um percurso do índice desejado até os nós acima que continuam a cobrir o intervalo.

Felizmente, dado um índice, isolar o bit $1$ menos significativo é uma tarefa fácil. Denote um número qualquer $x$ por $x=a1b$ em que $a$ é a porção dos bits que ocorrem antes do bit $1$ menos significativo de $x$ e $b$ são os bits que ocorrem depois, os quais possuem valor $0$.

De acordo com a aritmética de complemento de $2$, sabemos que $-x = \sim x +1$, e portanto que $-x = \sim (a\mathbf{1}b) +1$. Mas $\sim(a\mathbf{1}b) = (\sim a)\mathbf{0}11\ldots 1$ e portanto, $\sim (a\mathbf{1}b)+1 = (\sim a)\mathbf{1}0\ldots 0$.

Logo, para isolar o bit mais significativo de $x$ , basta fazer x & -x uma vez que:

       a  1 b
     (~a) 1 b 
  & -----------
    0...010...0

Com o disposto acima, para calcular $sum(1,i)$ basta realizar o seguinte procedimento sobre ft:

int sum(int i){
    int sum = 0;
    while(i>0){
        sum+=ft[i];
        i -= (i & -i);
    }
    return sum;
}

Para calcular $sum(i,j)$, basta aplicar o procedimento anterior com parâmetros $j$ e $i-1$ e subtrair um do outro, conforme o código abaixo:

int sum(int i,int j){
    return sum(j) - sum(i-1);
}

Atualizando Valores

Para que uma atualização de v[i] seja refletida em ft, é preciso atualizar os nós que compõem o intervalo $[1,i]$. Note que os valores $sum(1,k)$ com $1\leq < i$ continuarão intactos. Assim só é necessário atualizar os nós que envolvem o índice $i$, o que pode ser feito de uma forma análoga à consulta, mas considerando os índices à direita de $i$.

void update(int i,int val){
    while(i<n){
        ft[i] += val;
        i += (i & -i);
    }
}

Tomando o índice $i=5$ como exemplo, teríamos que atualizar os seguintes índices de ft: 101 (3), 110 (6) e 1000 (8).

Implementação

Consolidando todos os conceitos, temos o seguinte resultado. Podemos ver que a implementação é bem compacta e mais simples do que a de uma árvore de segmentos.

#include <iostream>
#include <vector>

using namespace std;

class fenwick_tree{
public:
    
private:
    vector<int> ft;
    size_t n;

public:
    fenwick_tree(vector<int>& v){
        vector<int> c = v;
        n = v.size();
        // Cria a soma cumulativa
        cout << " c = ";
        for(size_t i=1;i<v.size();i++){
            c[i] = c[i-1]+v[i];
            cout << c[i] << " ";
        }
        cout << endl;
        build_ft(c);
    }
    int sum(int i){
        int sum = 0;
        while(i>0){
            sum+=ft[i];
            i -= (i & -i);
        }
        return sum;
    }
    int sum(int i,int j){
        return sum(j) - sum(i-1);
    }
    void update(int i,int val){
        while(i<n){
            ft[i] += val;
            i += (i & -i);
        }
    }

private:
    void build_ft(vector<int>& c){
        // Inicializa ft
        cout << "ft = ";
        ft.assign(c.size(),0);
        for(size_t i=1;i<c.size();i++){
            size_t offset = (i & -i);
            ft[i] = c[i] - c[i-offset];
            cout << ft[i] << " ";
        }
        cout << endl;
    }
};
int main(){
    // Vetor com base no índice 1.
    vector<int> v = {0,1,3,2,5,2,8,7,3,0,4};
    fenwick_tree fent(v);
    for(size_t i=1;i<v.size();i++){
        cout << "sum(" << i << ") = " << fent.sum(i) << endl;
    }
    cout << "Atualizando FT" << endl;
    fent.update(3,-1);
    fent.update(2,5);
    for(size_t i=1;i<v.size();i++){
        cout << "sum(" << i << ") = " << fent.sum(i) << endl;
    }
    cout << "sum(2,6) = " << fent.sum(2,6) << endl;
    return 0;
}

Complexidade

Como as árvores de Fenwick possuem altura no máximo $O(\lg n)$ as operações de $sum$ e $update$ são executadas neste tempo.

Leituras Recomendadas

• Referência C++
• Implementação de um Deque
• Guia para utilização de um map
• Tutorial Topcoder de Fenwick Trees