A programação dinâmica (PD) possui diversas técnicas de otimização, sendo uma das mais importantes a utilização de árvores de segmentos. Este artigo apresenta os tipos mais comuns desse método, seus padrões e alguns exemplos práticos.

Pré-requisitos: Programação dinâmica linear e conhecimento sobre árvores de segmentos.

Definições

Para facilitar o entendimento, estabelecemos as seguintes definições (que podem não ser unviersalmente adotadas):

• Atual: Refere-se ao valor da PD em processamento e às informações relevantes na iteração atual.
• Decisão: O processo de atualização do valor da PD, equivalente a uma transição.
• Ponto de decisão: A origem de uma transição para um valor da PD (se o valor de (dp_i) é derivado de (dp_j + x) e (dp_j + x) é o valor ótimo, então (j) é o ponto de decisão).
• Valor da decisão: O valor resultante da transição.

Tomando como exemplo a maior subsequência crescente.

Suponha que estamos calculando (dp_i). Neste contexto, (dp_i) é o valor atual da PD, e (a_i) é a informação atual.

Se (dp_i) pode ser obtido a partir de (dp_j + 1) (com (a_j < a_i)), então (j) é o ponto de decisão e (dp_j + 1) é o valor da decisão.

Classificação

Classifico as otimizações de PD com árvores de segmentos em três categorias principais, baseadas em suas aplicações distintas:

• Consulta e Atualização Normais: Quando precisamos rapidamente obter informações como o valor máximo em um intervalo, geralmente usados em métodos de preenchimento de tabelas.
• Manutenção de Arrays: Quando inserimos o array da PD na árvore de segmentos, frequentemente aplicado em métodos de propagação de tabelas.
• Manutenção de Valores de Decisão: Quando dinamicamente mantemos as respostas de todos os pontos de decisão.

Os métodos Consulta e Atualização Normais e Manutenção de Arrays são basicamente intercambiáveis, mas a última exige mais esforço cognitivo.

Consulta e Atualização Normais / Manutenção de Arrays

Exemplo: Observação de Animais (CF1304F)

Versão Fácil

Seja (f_{i,j}) o número de fotos no dia (i) com o intervalo começando em (j).

Obtemos uma solução PD (O(nm^2)) ao enumerar as posições anteriores e atuais (j) e (l).

No entanto, quando os intervalos ([j,j+k-1]) e ([l,l+k-1]) não se interceptam, a contribuição da foto atual independe da posição de (j), permitindo consultas rápidas com máximos prefixo e sufixo. Apenas (O(k)) intervalos possuem interseção, que podem ser enumerados diretamente. Isso resulta em uma solução (O(nmk)).

Versão Difícil

Consideremos otimizar as transições quando há interseção de intervalos.

Seja (sum_i) o prefixo acumulado da linha (i).

Nesta versão, enumeramos apenas (l). Para (l <= j), a contribuição da linha é (f_{i-1,j} + sum_{i,j-1} - sum_{i,l-1}). Para maximizar isso, basta maximizar (f_{i-1,j} + sum_{i,j-1}), o que pode ser feito com uma árvore de sgementos para máximo em intervalos. O caso (l > j) é tratado de forma similar.

Trata-se de uma árvore de segmentos simples para atualização pontual e consulta de máximo em intervalos, um exemplo básico de Consulta e Atualização Normais.

A Manutenção de Arrays inverte essa abordagem, enumerando (j) e aplicando operações de máximo em um segmento de (f_{i,l}). A vantagem é a manutenção em tempo real do array da PD, mas a desvantagem é a complexidade de pensamento exigida, além de que este problema requer atualizações em intervalos.

"Mas isso não poderia ser resolvido com uma fila monotônica?"

"Sim, mas nosso foco é a otimização de PD com árvores de segmentos."

Embora a complexidade da árvore de segmentos seja (O(\log n)), a abordagem é mais conveniente e exige menos esforço cognitivo!

Código (Consulta e Atualização Normais):

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j + k - 1 <= m; j++)
    {
        if (i > 1)
        {
            if (k < j)
                dp[i][j] = max(dp[i][j], max_prefixo[i - 1][j - k]);
            if (j + k + k - 1 <= m)
                dp[i][j] = max(dp[i][j], max_sufixo[i - 1][j + k]);
            dp[i][j] = max(dp[i][j], arvore1[i - 1].consulta(1, 1, tamanho, j - k + 1, j) + s[i][j - 1]);
            dp[i][j] = max(dp[i][j], arvore2[i - 1].consulta(1, 1, tamanho, j, j + k - 1) - s[i][j + k - 1]);
        }
        dp[i][j] += soma(i, j) + soma(i + 1, j);
        max_prefixo[i][j] = max(max_prefixo[i][j - 1], dp[i][j]);
        arvore1[i].atualiza(1, 1, tamanho, j, dp[i][j] - s[i + 1][j + k - 1]);
        arvore2[i].atualiza(1, 1, tamanho, j, dp[i][j] + s[i + 1][j - 1]);
    }
    for (int j = m - k + 1; j >= 1; j--)
        max_sufixo[i][j] = max(max_sufixo[i][j + 1], dp[i][j]);
}

Subsequências (CF597C)

Dada uma permutação (a) de (1) a (n), calcule o número de subsequências crescentes de comprimento (m+1) em (a). (1 \le n \le 10^5), (0 \le m \le 10), (1 \le a_i \le n), resposta não excede (8 \times 10^{18}).

Primeiro, definimos a PD: (dp_{i,k}) representa o número de subsequências crescentes de comprimento (k) terminando em (i).

A transição é:

[dp_{i,k}=\sum_{j=0}^{i-1} dp_{j,k-1} (a_j < a_i) ]Sem a restrição (a_j < a_i), poderíamos usar uma soma de prefixo para otimizar. Com essa restrição, podemos reescrever:

[dp_{i,k}=\sum_{l=1}^{a_i - 1}\sum_{j=0}^{i-1} dp_{j,k-1} (a_j = l) ]Se definirmos (s_{i,k,x}) como (\sum_{j=0}^{i-1} dp_{j,k} (a_j = x)), então:

[dp_{i,k}=\sum_{l=1}^{a_i - 1}s_{i,k-1,l} ]Aqui, fica claro que podemos usar uma árvore de segmentos no domínio dos valores, armazenando (s_{i,k-1,l}) na posição (l) da árvore. Enumerando (k), (dp_{i,k}) é simplesmente a consulta da soma no intervalo ([1, a_i-1]) da árvore.

Atualização pontual e soma em intervalo. Uma árvore de Fenwick também seria adequada.

Complexidade de tempo (O(nk \log n)).

Ônibus AUT (P3431)

Primeiro discretizamos, depois enumeramos as coordenadas x e y. A transição vem da coordenada x anterior, com posições válidas sendo todas as coordenadas y menores ou iguais à atual. No entanto, essa abordagem tem complexidade insatisfatória!

Notamos que podemos manter apenas os pontos-chave (onde há pessoas), ordenando por coordenada x.

Atualização pontual e máximo de prefixo. (O(k \log k)).

Pilares (CF474E)

Similar à manutenção de subsequências crescentes, usando uma árvore de segmentos no domínio dos valores para atualização pontual e máximo de prefixo/sufixo.

Caminhos (CF960F)

Primeiro, temos uma ordenação bidimensional, então enumeramos as arestas de entrada, removendo uma dimensão e restando o domínio dos valores.

Definimos (dp_i) como o número de caminhos terminando na aresta (i). Precisamos satisfazer duas condições:

• O vértice final da aresta de decisão deve ser igual ao vértice inicial da aresta atual
• O peso da aresta de decisão deve ser menor que o peso da aresta atual

Sem a primeira condição, poderíamos usar uma árvore de segmentos no domínio dos valores. Com a primeira condição, precisaríamos de (n) árvores de segmentos, exigindo abertura dinâmica de nós.

Complexidade de tempo (O(m \log \max{w_i})), com complexidade de espaço também (O(\log)).

Manutenção de Valores de Decisão

Primeiro, aprendi essa abordagem no blog do lsj2009, pelo qual agradeço imensamente!

A ideia é imaginar um array onde o valor na posição (j) representa a contribuição para a posição atual (i). Em outras palavras, trata-se de algo como (f_i = \max{g_j}), onde (g_j) é esse array.

Se a equação de transição da PD tem uma contribuição dinâmica, provavelmente podemos usar uma árvore de segmentos para rastrear as mudanças nos valores de decisão.

Esses problemas podem ser difíceis de resolver inicialmente, mas uma vez compreendida a abordagem de Manutenção de Valores de Decisão, eles se tornamtotalmente padronizados e mais fáceis de resolver.

Padaria (CF833B)

Suponha que já temos o array de valores de decisão do round anterior (i-1), ou seja, (g_j = f_j + w(j+1,i-1)), onde (w(j+1,i-1)) é o número de cores de (j+1) a (i-1). Quando (i-1) se torna (i), vejamos o que acontece!

Este é o array (g) quando (i=6):

Podemos facilmente obter (f[6]) como (\max_{0 \le j < 6} g_j).

E este é o array (g) quando (i=7):

Como podemos transformar o array (g) de (i-1) para o atual? Notamos que os valores em vermelho aumentaram em 1, ou seja, o número de cores à direita aumentou. No entanto, (g_0) e (g_1) não mudaram, pois a posição 2 já era azul e adicionar outro azul não altera a contagem de cores.

Portanto, chegamos à conclusão: seja (lst) a última ocorrência da cor da posição (i), então precisamos apenas adicionar 1 aos valores de (g) no intervalo ([lst, i)). Além disso, devemos adicionar (f_{i-1}) a (g_{i-1}).

Árvore de segmentos suportando adição em intervalo e máximo em intervalo.

Além disso, o problema limita o número de intervalos, então adicionamos uma dimensão e usamos (m) árvores de segmentos.

for (int i = 1; i <= n; i++)
{
    for (int j = 1; j <= m; j++)
    {
        arvore[j - 1].atualiza(1, 0, n, i - 1, i - 1, dp[i - 1][j - 1]);
        arvore[j - 1].atualiza(1, 0, n, anterior[a[i]], i - 1, 1);
        dp[i][j] = arvore[j - 1].consulta(1, 0, n, 0, i - 1);
    }
    anterior[a[i]] = i;
}

Desafio Diário (P9871)

Primeiro, consideremos como fazer em (O(n \log n)).

Usamos o mesmo método. Primeiro, precisamos escrever na forma (f_i = \max g_j). Uma ideia é definir (f_i) como forçando a seleção da posição (i), mas isso não permite saber quantos dias corridos consecutivos temos!

Se forçarmos (j) dias sem correr e todos os dias de (j+1) a (i-1) correndo, podemos verificar a condição de corrida consecutiva. Portanto, definimos (f_i) como o mínimo energia necessário a partir do dia (i) sem correr, ou equivalentemente, o máximo prefixo da definição original de (f_{i-1}).

Agora, consideramos o que precisa mudar em (g) quando passamos de (i-1) para (i). O problema informa que correr um dia consome (d) de energia, e completar um desafio concede energia. Primeiro, como forçamos todos os (j) a correrem de (j+1) a (i-1), precisamos subtrair (d) de todos os (g) em ([1, i-1]). Em seguida, enumeramos os desafios com (i) como extremo direito, então os (g) em ([1, l-1]) devem ter (v) adicionado.

Finalmente, note que o problema proíbe correr mais de (k) dias consecutivos, então basta consultar o máximo de (g) em ([i-k, i-1])!

Não se esqueça de adicionar (\max_{0 \le i < i} f_i) a (g_i).

Para otimizar este (O(n \log n)), precisamos manter apenas as posições (l-1) e (r), pois são as únicas úteis.

Árvore de segmentos suportando adição em intervalo e máximo em intervalo.

Complexidade de tempo (O(m \log m)).

Clique para ver o código``` void resolver() { scanf("%d%d%d%lld", &n, &m, &k, &d); lista_valores[++pos] = 0; for (int i = 1; i <= m; i++) { scanf("%d%d%d", &desafios[i].direita, &desafios[i].esquerda, &desafios[i].valor); desafios[i].esquerda = desafios[i].direita - desafios[i].esquerda + 1; lista_valores[++pos] = desafios[i].direita; lista_valores[++pos] = desafios[i].esquerda - 1; } sort(lista_valores + 1, lista_valores + pos + 1); pos = unique(lista_valores + 1, lista_valores + pos + 1) - lista_valores - 1; sort(desafios + 1, desafios + m + 1); for (int i = 1; i <= m; i++) consultas[busca_binaria(desafios[i].direita)].push_back(i); for (int i = 1; i <= pos; i++) { arvore.atualiza(1, 1, pos, i, i, resposta); arvore.atualiza(1, 1, pos, 1, i - 1, -d * (lista_valores[i] - lista_valores[i - 1])); for (auto j : consultas[i]) arvore.atualiza(1, 1, pos, 1, busca_binaria(desafios[j].esquerda - 1), desafios[j].valor); f[i] = arvore.consulta(1, 1, pos, busca_binaria(lista_valores[i] - k), i - 1); resposta = max(rseposta, f[i]); } printf("%lld\n", resposta); }

### Estante de Livros G (P1848)

A este ponto, se você já entendeu essa abordagem, pode resolver problemas similares diretamente aplicando o padrão. Tente resolver este problema da USACO usando essa técnica. Há também um problema praticamente idêntico (com apenas um \(h_i\)) em P1295 \[TJOI2011\] Estante de Livros.

A fazer:

- P11456 \[USACO24DEC\] Intervalos Interestelares G