Suma de valores por prefijo
La misión
Problema
Diseña un almacén de claves de tipo string (cadena) con valores enteros y dos operaciones. put(key, value) asigna el valor de una clave y reemplaza el anterior si la clave ya existe. total(prefix) devuelve la suma de los valores de las claves que empiezan con el prefijo, o 0 si no hay ninguna. Ambas operaciones deben costar un tiempo proporcional a la longitud de su argumento.
Ejemplos
Input: put("apple", 3), total("ap"), put("app", 2), total("ap"), total("apple")
Output: 3, 5, 3
Por qué: después de los dos put, "ap" es el comienzo de ambas claves y "apple" solo de una
Input: put("apple", 3), put("app", 2), put("apple", 5), total("ap")
Output: 7
Por qué: el segundo put de "apple" reemplaza 3 por 5 en vez de sumarle
Input: put("apple", 3), total("b")
Output: 0
Por qué: caso límite: ninguna clave empieza con el prefijo
Pistas
0 / 3
Sumar todas las claves que coinciden en el momento de la consulta cuesta tiempo por cada clave bajo el prefijo. Intenta tener la respuesta lista antes de que llegue la pregunta.
En un árbol de prefijos, las claves que empiezan con un prefijo son exactamente las claves que están debajo del nodo de ese prefijo. Cada nodo puede guardar la suma acumulada de todo lo que tiene debajo.
En put, calcula cuánto cambia el valor de la clave, que es el valor nuevo menos el anterior o cero, y suma esa diferencia a cada nodo del camino de la clave. En total, baja hasta el nodo del prefijo y devuelve la suma que guarda.
- Tiempo objetivo
- O(L)
- Espacio objetivo
- O(total characters)
Solución
Cada nodo del árbol de prefijos guarda la suma de los valores de todas las claves cuyo camino pasa por él, así que la respuesta para un prefijo es simplemente el número guardado en su nodo. Un put cambia esa suma exactamente en los nodos del camino de la clave, y solo en la diferencia entre el valor nuevo y el anterior, que recuerda un diccionario aparte; eso es lo que hace que sobrescribir una clave sea correcto en vez de contarla dos veces. Ambas operaciones tocan un nodo por carácter, así que cuestan O(L) para un argumento de longitud L, y el árbol usa O(total de caracteres guardados) de espacio.
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 0¿Lo que te frena es la idea y no el código? Búsqueda por prefijo lo explica.