Na véspera do próximo lançamento do curso Algoritmos para desenvolvedores, realizamos uma lição aberta . Eles conversaram sobre a conhecida idéia de uma árvore de segmentos, discutiram como construí-la, atualizá-la e rapidamente O(log n) calcula a soma dos números de qualquer segmento de uma determinada matriz. O algoritmo é muito simples e econômico: você precisa de O(n) memória. Para consolidar o material, eles resolveram o problema das olimpíadas.
O webinar foi conduzido por um programador e professor experientes, bem como pelo diretor do curso "Algoritmos para Desenvolvedores",
Evgeny Volosatov .
O ditado
Uma árvore de segmentos é uma estrutura de dados que permite encontrar rapidamente algoritmicamente simples e logarítmica a soma dos elementos de uma matriz em um determinado segmento.
Por exemplo, imagine que você precisa encontrar a soma dos seguintes números:
Além disso, precisamos não apenas calcular a soma dos números da sequência especificada (a soma dos elementos de uma determinada matriz), mas o
mais rápido possível para encontrar a soma de qualquer sequência desses números . Ou seja, podemos pedir algum intervalo (segmento) e dar a resposta o mais rápido possível, qual é a soma dos números desse intervalo:
O que significa rápido? Isso significa
mais rápido do que se simplesmente adicionássemos os números . Afinal, pode haver milhões e bilhões de números ...
Era o desejo de encontrar rapidamente a soma de elementos consecutivos que se tornaram a motivação para o nosso webinar. Além disso, estamos falando não apenas da soma, mas também de outras tarefas, por exemplo, calcular qualquer função associativa. Portanto, estamos falando de operações cuja execução não depende da ordem de cálculo.
Vamos retornar à nossa linha:
Obviamente, se queremos encontrar o resultado rapidamente, precisamos calcular alguns valores com antecedência. A primeira coisa que vem à mente é dobrar em pares:
Agora, se você precisar encontrar a soma dos números, podemos fazê-lo quase instantaneamente. Por exemplo, para encontrar a soma do segmento mencionado acima, basta adicionar 13 a 9. Tudo é elementar: para encontrar a
soma de quatro números, adicionamos
apenas dois .
Nós complicamos a tarefa:
Para encontrar a soma desse segmento, precisamos adicionar os elementos que, de uma forma ou de outra, cobrem nosso segmento:
Claro, 3 + 13 + 19 = 35. Observe que para encontrar a
soma dos sete números , adicionamos
apenas três . Se o segmento consistisse em mil elementos, seria suficiente adicionar uma média de 10 elementos, pois temos uma complexidade logarítmica com um logaritmo de base 2. E é rápido!
Árvore binária completa
Uma árvore binária completa é uma árvore, cada elemento com exatamente dois filhos.
Para trabalhar com uma árvore binária completa, você pode e deve usar uma estrutura de dados como uma matriz.
Numerar essa matriz é conveniente a partir de uma . Numeramos cada elemento da árvore binária com números naturais de 1 a 2
n -1:
A beleza da abordagem é que é muito fácil calcular o número de filhos e pais.
A fórmula para calcular o "filho esquerdo":
i * 2 , o "direito":
i * 2 + 1 .
Por exemplo, calculamos o número de filhos no quinto elemento:
- 5 x 2 = 10 ;
- 5 x 2 + 1 = 11 .
E como do "filho" subir para o "pai"? Usamos
divisão inteira i / 2Ok, e como determinar se a criança é esquerda ou direita? A resposta é a seguinte:
filhos da esquerda têm números pares, filhos da direita têm números ímpares .
Lembre-se destes pontos.
Voltando ao nosso exemplo de uma árvore binária, nos perguntamos: como podemos construí-la? Olha, primeiro temos uma matriz de números:
Para isso, você precisa construir uma árvore binária. Quanta memória é necessária para armazenar a árvore binária, na parte inferior da qual são esses elementos?
A resposta a esta pergunta é
2n se
n for uma potência de dois.
Vamos mais longe, porque mais duas perguntas surgem diante de nós:
- de qual elemento você precisa colocar os números de origem em uma matriz de uma árvore binária completa?
- de qual elemento e em qual direção começaremos a encher nossa árvore com valores pré-calculados?
A resposta para a primeira pergunta é bastante simples: temos 8 elementos, no total, haverá 16 elementos na matriz, o que significa que o primeiro elemento será numerado de 16 a 8 = 8. E começaremos a construir da esquerda para a direita e de baixo para cima, começando no elemento 7, somando valores em filhos, assim:
Em seguida, você precisa determinar como encontrar a soma do segmento desejado. Vamos voltar ao nosso primeiro exemplo, numerar os elementos e definir um segmento, e denotamos o primeiro elemento no segmento a ser adicionado pela letra L e o último por R:
Agora é necessário introduzir mais um conceito para que o algoritmo de ações seja claro. Estamos falando do conceito de elementos fundamentais e seus segmentos fundamentais correspondentes. O elemento fundamental é qualquer elemento de toda a matriz e o segmento fundamental corresponde a ele, ou seja, os elementos da matriz inicial que são seus filhos / netos imediatos. Para o elemento fundamental com o número 4 "5", o segmento fundamental será de 8 a 9 elementos: ["2"; "3"]:
Quanto ao elemento fundamental com o número 10 - “7” (designado L), ele coincide com o seu segmento fundamental. É possível expandir esse segmento fundamental sem ir além da LR? No nosso caso, você pode. A regra para a borda esquerda é a seguinte: se for um filho esquerdo, o segmento fundamental poderá ser expandido, o novo elemento fundamental será o pai do atual. Ou seja, podemos escrever o seguinte no programa:
Agora, vamos para o elemento direito R. É um elemento fundamental e um filho esquerdo, para que não possamos mais expandir a área (iremos além do segmento). Portanto, podemos adicionar este elemento à resposta:
Em seguida, você precisa do elemento esquerdo para mover para a direita e o direito para a esquerda. Para o elemento esquerdo com índice L = 10, o próximo índice é 5, porque irá para o pai. Mas vai primeiro para a direita e depois para cima:
Portanto, o valor de L passou para um nível superior e um pouco para a direita. Como o R diminuirá? Usando a fórmula (R - 1) / 2.
Aqui está um algoritmo desse tipo. Quanto aos seguintes valores das variáveis L e R, eles serão movidos da seguinte forma:
Se não houver 8 elementos na árvore, mas um número inconveniente, digamos 12, teremos que adicionar a árvore (a árvore binária deve estar completa) a 16.
A fórmula para calcular o número de elementos (toda a parte do logaritmo é usada):
Agora calculamos a função associativa de encontrar o
mínimo . Aqui está nossa árvore e corte:
Quantas vezes você acha que o elemento 5 estará envolvido em nossa função - uma ou duas? Claro que sim, mas como isso é verificado no algoritmo? De fato, esse elemento é um filho esquerdo ou direito, o que significa que a ação será executada para L ou R.
+
Agora considere a operação de alteração. Suponha que algum elemento tenha sido alterado, por exemplo, em vez de 7, 0. Para que nossa árvore de segmentos permaneça em condições de trabalho, precisamos atualizar todos os pais e precisamos ir ao topo.
Solução do problema das olimpíadas
Um dos requisitos para essas tarefas é que tudo funcione rapidamente. Portanto, temos a seguinte condição:
Vamos resolver usando conhecimento sobre a árvore de segmentos. Como resultado, obtemos o seguinte código C #:
Enviamos para verificação, vemos que a
decisão foi tomada e está completa , o que significa que nosso algoritmo funciona.
Isso é tudo, se você quiser mais detalhes,
assista ao vídeo inteiro . Você também pode ler à vontade os seguintes artigos do autor da nossa professora
Evgeny Volosatov em Habré:
-
Balanceamento de árvores vermelho-preto - Três casos ;
-
O cavalo se move em pedaços. Xadrez Bitboard .