Skip to content

Latest commit

 

History

History
86 lines (50 loc) · 4.89 KB

11-Arvore_de_Segmentos.md

File metadata and controls

86 lines (50 loc) · 4.89 KB
Raw

Árvore de Segmentos (Segment Tree) 🌳

Nesse texto vamos falar um pouco a respeito de uma estrutura de dados muito poderosa e muito utilizada na maratona: a Árvore de segmentos.

Comecemos falando a respeito de um problema: o Range Sum Query (RSQ)

Range Sum Query ➕

Dado um vetor a, realizaremos Q queries, isto é, perguntas do tipo:

Qual é a soma dos elementos do vetor no intervalo de l à r?

Denotaremos essa operação rsq(l, r).

Estratégia Naive (ingênua) 🤔 :

Na estratégia Naive, simplesmente realizaremos a soma entre os elementos do intervalo dado:

rsq(l, r) = a[l] + a[l+1] + ... + a[r-1] + a[r]

  • Complexidade: O(n) por query.

Soma acumulada 💰 :

Nesta estratégia, criaremos um vetor de soma acumulada e utilizaremos a subtração entre somas de prefixos para calcular a soma em um determinado intervalo.

O vetor de soma acumulada representa a soma até um certo índice i, isto é:

acc[i] = a[1] + a[2] + ... + a[i]

Para construirmos o vetor de soma acumulada, sabemos de duas igualdades:

\begin{align*} &acc[i] = a[1] + a[2] + ... + a[i] \\ &acc[i-1] = a[1] + a[2] + ... + a[i-1] \end{align*}

\center{\therefore acc[i] = acc[i-1] + a[i]}

Utilizando o vetor acc, podemos calcular a soma em um intervalo (l,r), denominada rsq(l,r), da seguinte forma:

\begin{align*} &acc[l-1] = a[1] + a[2] + ... + a[l-1] \\ &acc[r] = \underbrace{a[1] + a[2] + ... + a[l-1]}_{{acc[l-1]}} + \underbrace{a[l] + a[l+1] + ... + a[r]}_{{rsq(l,r)}} \end{align*}

\center{\therefore acc[r] - acc[l-1] = rsq(l,r)}

  • Complexidade: O(1) \text{ por query.}

Vamos complicar um pouquinho então... 😎:

Vamos definir um novo tipo de query possível: upd(k, x) , isto é, atualizar/sobreescrever (realizar um update) o elemento k com o valor x.

Mas como isso afetou as estratégias citadas?

Com essa mudança, ambas as estratégias serão O(n) em geral:

  • Soma acumulada:

    • O(1) para calcular rsq(l, r).
    • O(n) para realizar upd(k, x), visto que o vetor acc dever ser reconstruído.

  • Estratégia naive:

    • O(n) para calcular rsq(l, r).
    • O(1) para realizar upd(k, x).

Mas existe uma solução! As tais Árvores de Segmentos!

  • Segment tree:

    • O(\log_2{(n)}) para calcular rsq(l, r).
    • O(\log_2{(n)}) para realizar upd(k, x).

Mas o que é essa tal Seg. Tree?

A árvore de segmentos é uma estrutura de dados que, como diz o nome, se organiza em segmentos. Cada nó dessa árvore contém informação de um intervalo/segmento (l,r).

Para o problema dado (RSQ), essa informação é a soma dos elementos do intervalo, mas é importante notar que a Segment Tree é uma estrutura muito poderosa que pode armazenar outras informações, como por exemplo o elemento máximo/mínimo naquele intervalo, e pode resolver uma variedade enorme de problemas de Programação Competitiva.

Seg tree