Solution: Map Sum Pairs
Explore how to design a MapSum data structure that supports inserting key-value pairs and retrieving prefix sums efficiently. Understand how to use a trie combined with a hash map to update values and compute prefix sums without scanning all keys. Learn to handle updates by propagating deltas and optimize performance for prefix queries.
We'll cover the following...
Statement
Design a data structure that supports the following operations:
Insert a key-value pair:
Each key is a string, and each value is an integer.
If the key already exists, update its value to (overriding the previous value).
Return the prefix sum:
Given a string,
prefix, return the total sum of all values associated with keys that start with this prefix.
To accomplish this, implement a class MapSum:
Constructor: Initializes the object.
void insert (String key, int val): Inserts the key-value pair into the data structure. If the key already exists, its value is updated to the new one.
int sum (String prefix): Returns the total sum of values for all keys that begin with the specified prefix.
Constraints:
key.length,prefix.length...