Map Sum Pairs

class MapSum {
    struct Node {
        Node* child[26]{};
        int sum = 0;
    };
    Node* root;
    unordered_map<string, int> stored;
public:
    MapSum() : root(new Node()) {}

    void insert(string key, int val) {
        int delta = val - stored[key];
        stored[key] = val;
        Node* cur = root;
        for (char c : key) {
            int i = c - 'a';
            if (!cur->child[i]) cur->child[i] = new Node();
            cur = cur->child[i];
            cur->sum += delta;
        }
    }

    int sum(string prefix) {
        Node* cur = root;
        for (char c : prefix) {
            int i = c - 'a';
            if (!cur->child[i]) return 0;
            cur = cur->child[i];
        }
        return cur->sum;
    }
};

type mapSumNode struct {
    child [26]*mapSumNode
    sum   int
}

type MapSum struct {
    root   *mapSumNode
    stored map[string]int
}

func Constructor() MapSum {
    return MapSum{root: &mapSumNode{}, stored: map[string]int{}}
}

func (m *MapSum) Insert(key string, val int) {
    delta := val - m.stored[key]
    m.stored[key] = val
    cur := m.root
    for i := 0; i < len(key); i++ {
        idx := key[i] - 'a'
        if cur.child[idx] == nil {
            cur.child[idx] = &mapSumNode{}
        }
        cur = cur.child[idx]
        cur.sum += delta
    }
}

func (m *MapSum) Sum(prefix string) int {
    cur := m.root
    for i := 0; i < len(prefix); i++ {
        idx := prefix[i] - 'a'
        if cur.child[idx] == nil {
            return 0
        }
        cur = cur.child[idx]
    }
    return cur.sum
}

from typing import Dict, List, Optional

class _Node:
    __slots__ = ('child', 'sum')

    def __init__(self) -> None:
        self.child: Dict[str, '_Node'] = {}
        self.sum = 0

class MapSum:
    def __init__(self) -> None:
        self.root = _Node()
        self.stored: Dict[str, int] = {}

    def insert(self, key: str, val: int) -> None:
        delta = val - self.stored.get(key, 0)
        self.stored[key] = val
        cur = self.root
        for ch in key:
            if ch not in cur.child:
                cur.child[ch] = _Node()
            cur = cur.child[ch]
            cur.sum += delta

    def sum(self, prefix: str) -> int:
        cur = self.root
        for ch in prefix:
            if ch not in cur.child:
                return 0
            cur = cur.child[ch]
        return cur.sum

class MapSum {
    constructor() {
        this.root = { child: new Map(), sum: 0 };
        this.stored = new Map();
    }

    insert(key, val) {
        const delta = val - (this.stored.get(key) || 0);
        this.stored.set(key, val);
        let cur = this.root;
        for (const ch of key) {
            if (!cur.child.has(ch)) cur.child.set(ch, { child: new Map(), sum: 0 });
            cur = cur.child.get(ch);
            cur.sum += delta;
        }
    }

    sum(prefix) {
        let cur = this.root;
        for (const ch of prefix) {
            if (!cur.child.has(ch)) return 0;
            cur = cur.child.get(ch);
        }
        return cur.sum;
    }
}

class MapSumNode {
    MapSumNode[] child = new MapSumNode[26];
    int sum;
}

class MapSum {
    private MapSumNode root;
    private Map<String, Integer> stored;

    public MapSum() {
        root = new MapSumNode();
        stored = new HashMap<>();
    }

    public void insert(String key, int val) {
        int delta = val - stored.getOrDefault(key, 0);
        stored.put(key, val);
        MapSumNode cur = root;
        for (int i = 0; i < key.length(); i++) {
            int idx = key.charAt(i) - 'a';
            if (cur.child[idx] == null) cur.child[idx] = new MapSumNode();
            cur = cur.child[idx];
            cur.sum += delta;
        }
    }

    public int sum(String prefix) {
        MapSumNode cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            int idx = prefix.charAt(i) - 'a';
            if (cur.child[idx] == null) return 0;
            cur = cur.child[idx];
        }
        return cur.sum;
    }
}

interface MapSumNode {
    child: Map<string, MapSumNode>;
    sum: number;
}

class MapSum {
    private root: MapSumNode;
    private stored: Map<string, number>;

    constructor() {
        this.root = { child: new Map(), sum: 0 };
        this.stored = new Map();
    }

    insert(key: string, val: number): void {
        const delta = val - (this.stored.get(key) ?? 0);
        this.stored.set(key, val);
        let cur = this.root;
        for (const ch of key) {
            if (!cur.child.has(ch)) cur.child.set(ch, { child: new Map(), sum: 0 });
            cur = cur.child.get(ch)!;
            cur.sum += delta;
        }
    }

    sum(prefix: string): number {
        let cur = this.root;
        for (const ch of prefix) {
            if (!cur.child.has(ch)) return 0;
            cur = cur.child.get(ch)!;
        }
        return cur.sum;
    }
}