如何用 Trie 实现前缀键值求和（MapSum）？

简化版

Trie 节点维护一个 sum，表示以该节点前缀开头的所有 key 的 value 总和。插入 key 时如果 key 已存在，要先算出增量 delta = newVal - oldVal，沿路径每个节点加上 delta；查询前缀时走到前缀节点返回 sum。

详细版

MapSum 支持两个操作：

insert(key, val)：设置 key 的值，重复插入同一个 key 时覆盖旧值。
sum(prefix)：返回所有以 prefix 开头的 key 的 value 总和。

做法：

用哈希表 values 记录每个 key 当前值。
插入时计算增量 delta = val - values.getOrDefault(key, 0)。
把 key 插入 Trie，沿途每个节点的 sum += delta。
查询 prefix 时沿 Trie 走到终点，若走不通返回 0，否则返回该节点 sum。

void insert(String key, int val) {
    int delta = val - values.getOrDefault(key, 0);
    values.put(key, val);
    Trie node = root;
    node.sum += delta;
    for (char ch : key.toCharArray()) {
        int i = ch - 'a';
        if (node.children[i] == null) node.children[i] = new Trie();
        node = node.children[i];
        node.sum += delta;
    }
}

这样 insert 是 O(L)，sum(prefix) 是 O(P)，不需要每次查询都遍历所有 key。

完整版教学

一、为什么普通哈希表查前缀和很慢

哈希表适合完整 key 的等值查询，例如查 apple 的值是 3。但如果要查所有以 ap 开头的 key 的和，哈希表没有前缀索引，只能遍历所有 key 并判断 startsWith("ap")。当 key 数量是 100000 时，每次前缀求和都扫全表会很慢。

Trie 把共同前缀压到同一个节点。只要在节点上维护“这个前缀下面所有 key 的总值”，查询前缀就变成走 P 个字符到节点，然后直接读 sum。这就是用空间换查询速度。

keys:
app=2
apple=3
bat=4

prefix "ap" 对应节点 sum = 2 + 3 = 5
prefix "ba" 对应节点 sum = 4

二、节点 sum 的含义要说清楚

每个 Trie 节点对应一个前缀。节点上的 sum 不是当前字符的值，也不是经过次数，而是“所有以该前缀开头的完整 key 的 value 总和”。根节点可以维护所有 key 的总和，也可以不用，看实现习惯。

插入 app=2, apple=3:

root
└─ a(sum=5)
   └─ p(sum=5)
      └─ p(sum=5, isEnd app)
         └─ l(sum=3)
            └─ e(sum=3, isEnd apple)

查询 sum("app") 返回 5，因为 app 和 apple 都以 app 为前缀。查询完整 key 和查询前缀在这道题里不是同一个操作。

三、覆盖旧值为什么必须用 delta

MapSum 的高频坑是重复插入同一个 key。比如先 insert("apple", 3)，再 insert("apple", 2)，最终 apple 的值应该是 2，而不是 5。如果每次沿路径直接加新值，就会把旧值重复累计。

错误做法：
apple=3 -> 节点加 3
apple=2 -> 节点再加 2
sum("app") = 5  // 错，应该是 2

正确做法：
delta = 2 - 3 = -1
沿 apple 路径每个节点加 -1
sum("app") 从 3 变成 2

因此要用额外哈希表保存 key 当前值。Trie 负责前缀聚合，哈希表负责覆盖语义，两者缺一不可。

四、插入和查询的代码骨架

插入时沿 key 的每个字符创建节点并累加 delta；查询时只沿 prefix 走，不需要 DFS 子树。这个区别很重要：如果节点已经维护了 sum，查询就是 O(P)，不是 O(子树大小)。

int sum(String prefix) {
    Trie node = root;
    for (char ch : prefix.toCharArray()) {
        int i = ch - 'a';
        if (node.children[i] == null) return 0;
        node = node.children[i];
    }
    return node.sum;
}

如果没有在节点维护 sum，也可以查询时走到前缀节点后 DFS 累加所有终止 key 的值，但那会把查询复杂度变成子树大小，失去 MapSum 的主要优势。

五、复杂度与空间权衡

设 key 长度为 L，prefix 长度为 P。插入只走 key 路径，所以是 O(L)；查询只走 prefix 路径，所以是 O(P)。空间是 Trie 节点数加哈希表，最坏约为所有 key 长度之和。

方案	插入	前缀求和	空间	备注
哈希表全扫	`O(1)` 更新	`O(N*P)` 或更高	较低	查询慢
Trie DFS	`O(L)`	`O(P + 子树大小)`	中高	不维护 sum
Trie 节点 sum	`O(L)`	`O(P)`	中高	查询最快

如果查询远多于插入，节点维护 sum 很划算。如果插入频繁且 key 很长，也要考虑 Trie 的空间成本。

常见误区与追问

记忆钩子：MapSum 的 Trie 节点不是只存路径，还要存“这个前缀下面的聚合值”。

误区：重复 insert 时直接加新 val。 这会重复累计旧值，必须用 delta = 新值 - 旧值。
误区：sum(prefix) 要 DFS 整个子树。 如果节点维护了 sum，走到前缀节点直接返回即可。
误区：只用 Trie 就够了。 覆盖旧值需要知道 key 原来的值，因此还要哈希表。
追问：前缀不存在返回什么？ 返回 0，因为没有任何 key 以该前缀开头。
追问：根节点要不要维护 sum？ 可选；维护后 sum("") 可以返回所有 key 总和。
追问：支持删除怎么做？ 删除等价于 insert(key, 0) 或沿路径加 -oldVal，再按需清理节点。

加强记忆

MapSum 是 Trie 和聚合信息结合的典型题。Trie 负责把相同前缀定位到同一个节点，节点 sum 负责保存该前缀下所有 key 的 value 总和，哈希表负责记录旧值以处理覆盖。记忆时抓住“插入走全 key 加 delta，查询走 prefix 读 sum”：一个是更新聚合，一个是读取聚合。这样遇到前缀计数、前缀权重、目录大小统计等问题，也能想到在 Trie 节点上挂聚合字段。

简化版

详细版