Prefix'e göre değer toplamı
Görev tanımı
Problem
Tam sayı değerli string anahtarlardan oluşan, iki işlemli bir depo tasarla. put(key, value) bir anahtarın değerini ayarlar; anahtar zaten saklıysa eski değerin yerine geçer. total(prefix) prefix (önek) ile başlayan bütün anahtarların değerlerinin toplamını, hiç yoksa 0 döndürür. İki işlem de argümanlarının uzunluğuyla orantılı zamana mal olmalı.
Örnekler
Input: put("apple", 3), total("ap"), put("app", 2), total("ap"), total("apple")
Output: 3, 5, 3
Neden: iki put'tan sonra "ap" iki anahtarı da, "apple" yalnız birini başlatıyor
Input: put("apple", 3), put("app", 2), put("apple", 5), total("ap")
Output: 7
Neden: "apple"ın ikinci put'u 3'ü üzerine eklemek yerine 5 ile değiştiriyor
Input: put("apple", 3), total("b")
Output: 0
Neden: edge case: hiçbir anahtar prefix ile başlamıyor
İpuçları
0 / 3
Sorgu anında eşleşen her anahtarı toplamak, prefix'in altındaki her anahtar için zamana mal olur. Cevabı soru sorulmadan önce hazır tutmaya çalış.
Bir trie'de bir prefix ile başlayan anahtarlar tam olarak o prefix'in düğümünün altındaki anahtarlardır. Her düğüm altındaki her şeyin kümülatif toplamını saklayabilir.
put'ta anahtarın değerinin ne kadar değiştiğini, yani yeni değer eksi eski değeri ya da sıfırı hesapla ve bu farkı anahtarın yolundaki her düğüme ekle. total'da prefix'in düğümüne in ve saklanan toplamını döndür.
- Hedef zaman
- O(L)
- Hedef alan
- O(total characters)
Çözüm
Trie'nin her düğümü, yolu ondan geçen her anahtarın değerlerinin toplamını tutar; bu yüzden bir prefix'in cevabı basitçe prefix'in düğümünde saklanan sayıdır. Bir put o toplamı tam olarak anahtarın yolu boyuncaki düğümlerde ve yalnız ayrı bir sözlüğün (dict) hatırladığı yeni değer ile eski değer arasındaki fark kadar değiştirir; bir anahtarın üzerine yazmayı iki kez saymak yerine doğru yapan da bu. İki işlem de karakter başına bir düğüme dokunur; L uzunluğundaki bir argüman için her biri O(L) tutar, ağaç da O(saklanan toplam karakter) alan kullanır.
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 0Kodda değil de fikirde mi takıldın? Prefix arama bunu anlatıyor.