Soma de valores por prefixo
A missão
Problema
Projete um armazenamento de chaves string com valores inteiros e duas operações. put(key, value) define o valor de uma chave, substituindo o valor antigo se a chave já estiver armazenada. total(prefix) retorna a soma dos valores de todas as chaves que começam com o prefixo, ou 0 se não houver nenhuma. As duas operações devem custar tempo proporcional ao comprimento do seu argumento.
Exemplos
Input: put("apple", 3), total("ap"), put("app", 2), total("ap"), total("apple")
Output: 3, 5, 3
Por quê: depois dos dois puts, "ap" inicia as duas chaves e "apple" inicia só uma
Input: put("apple", 3), put("app", 2), put("apple", 5), total("ap")
Output: 7
Por quê: o segundo put de "apple" substitui 3 por 5 em vez de somar
Input: put("apple", 3), total("b")
Output: 0
Por quê: edge case: nenhuma chave começa com o prefixo
Dicas
0 / 3
Somar todas as chaves correspondentes na hora da consulta custa tempo para cada chave sob o prefixo. Tente ter a resposta pronta antes de a pergunta ser feita.
Em uma trie, as chaves que começam com um prefixo são exatamente as chaves abaixo do nó desse prefixo. Cada nó pode guardar a soma acumulada de tudo o que está abaixo dele.
No put, calcule quanto o valor da chave muda, que é o valor novo menos o antigo, ou menos zero se a chave for nova, e some essa diferença em todos os nós do caminho da chave. No total, desça até o nó do prefixo e retorne a soma guardada nele.
- Tempo-alvo
- O(L)
- Espaço-alvo
- O(total characters)
Solução
Cada nó da trie (árvore de prefixos) guarda a soma dos valores de todas as chaves cujo caminho passa por ele, então a resposta para um prefixo é simplesmente o número guardado no nó desse prefixo. Um put muda essa soma exatamente nos nós ao longo do caminho da chave, e só pela diferença entre o valor novo e o antigo, que um dicionário separado lembra; é isso que torna correta a sobrescrita de uma chave, em vez de contá-la duas vezes. As duas operações tocam um nó por caractere, então cada uma custa O(L) para um argumento de comprimento L, e a árvore usa espaço O(total de caracteres armazenados).
class PrefixSums:
def __init__(self):
self.root, self.value = {"#": 0}, {}
def put(self, key, val):
delta = val - self.value.get(key, 0) # overwrite, do not double count
self.value[key] = val
node = self.root
node["#"] += delta # the empty prefix covers all
for ch in key:
node = node.setdefault(ch, {"#": 0})
node["#"] += delta # every prefix of key gains delta
def total(self, prefix):
node = self.root
for ch in prefix:
if ch not in node:
return 0
node = node[ch]
return node["#"]
s = PrefixSums(); s.put("apple", 3)
print(s.total("ap")) # -> 3
s.put("app", 2)
print(s.total("ap"), s.total("apple")) # -> 5 3
s.put("apple", 5)
print(s.total("ap"), s.total("b")) # -> 7 0Travou na ideia, e não no código? Busca por prefixo explica isso.