Map Sum Pairs

Design a data structure that supports inserting key-value pairs and returning the sum of values of all keys that start with a given prefix. Pattern focus: Trie Prefix Counting. A prefix counter stored in trie nodes lets sum queries run quickly after updates.

Input Format

operations = insert/sum commands, keys = command keys or prefixes, values = values for insert commands

Output Format

sum results for each sum command in order

Constraints

  • 1 <= operations.length <= 10^5
  • Keys contain only lowercase English letters.
  • Values are integers in the range [-10^9, 10^9].

Examples

Example 1:

Input:

operations = ["insert","sum","insert","sum","sum"]
keys = ["apple","ap","app","ap","app"]
values = [3,0,2,0,0]

Output:

[3,5,5]

Explanation:

After inserting apple and app, the prefix sum for ap becomes 5.

Example 2:

Input:

operations = ["sum","insert","sum"]
keys = ["a","a","a"]
values = [0,1,0]

Output:

[0,1]

Explanation:

A sum before any insert is zero, then the inserted key contributes to the next query.

Example 3:

Input:

operations = ["insert","insert","sum","insert","sum"]
keys = ["apple","apple","ap","app","ap"]
values = [3,2,0,4,0]

Output:

[2,6]

Explanation:

Updating an existing key should replace the old contribution rather than adding a duplicate entry.

Loading...
Map Sum Pairs - Trie DSA Problem