1.2. Medium

208. Implement Trie (Prefix Tree)

208. Implement Trie (Prefix Tree)

class Trie:

    def __init__(self):
        self.root = {}
        self.word_end = -1


    def insert(self, word: str) -> None:
        curNode = self.root
        for c in word:
            if c not in curNode:
                curNode[c] = {}
            curNode = curNode[c]
        curNode[self.word_end] = True


    def search(self, word: str) -> bool:
        curNode = self.root
        for c in word:
            if c not in curNode:
                return False
            curNode = curNode[c]
        if self.word_end not in curNode:
            return False
        return True


    def startsWith(self, prefix: str) -> bool:
        curNode = self.root
        for c in prefix:
            if c not in curNode:
                return False
            curNode = curNode[c]
        return True


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

307. Range Sum Query - Mutable

307. Range Sum Query - Mutable

# Segment tree node
class Node(object):

    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.total = 0
        self.left = None
        self.right = None


class NumArray:

    def __init__(self, nums: List[int]):
        # BuildTree T(n) = 2 * T(n/2) = O(n)
        # helper function to create the tree from input array
        def createTree(nums, l, r):
            # base case
            if l > r:
                return None
            # leaf node
            if l == r:
                n = Node(l, r)
                n.total = nums[l]
                return n

            mid = (l + r) // 2

            root = Node(l, r)

            # recursively build the Segment tree
            root.left = createTree(nums, l, mid)
            root.right = createTree(nums, mid + 1, r)

            # Total stores the sum of all leaves under root
            # i.e. those elements lying between (start, end)
            root.total = root.left.total + root.right.total

            return root

        self.root = createTree(nums, 0, len(nums) - 1)

    def update(self, i: int, val: int) -> None:
        # updateTree T(n) = T(n/2) + O(1) = log(n)
        # Helper function to update a value
        def updateVal(root, index, val):
            # Base case. The actual value will be updated in a leaf.
            # The total is then propogated upwards
            if root.start == root.end:
                root.total = val
                return val

            mid = (root.start + root.end) // 2

            # If the index is less than the mid, that leaf must be in the left subtree
            if index <= mid:
                updateVal(root.left, index, val)

            # Otherwise, the right subtree
            else:
                updateVal(root.right, index, val)

            # Propogate the changes after recursive call returns
            root.total = root.left.total + root.right.total

            return root.total

        return updateVal(self.root, i, val)

    def sumRange(self, i: int, j: int) -> int:

        # QueryTree T(n) = O(logn + k)
        # Helper function to calculate range sum
        def rangeSum(root, i, j):
            # If the range exactly matches the root, we already have the sum
            if root.start == i and root.end == j:
                return root.total

            mid = (root.start + root.end) // 2

            # If end of the range is less than the mid, the entire interval lies
            # in the left subtree
            if j <= mid:
                return rangeSum(root.left, i, j)

            # If start of the interval is greater than mid, the entire inteval lies
            # in the right subtree
            elif i >= mid + 1:
                return rangeSum(root.right, i, j)

            # Otherwise, the interval is split. So we calculate the sum recursively,
            # by splitting the interval
            else:
                return rangeSum(root.left, i, mid) + rangeSum(root.right, mid + 1, j)

        return rangeSum(self.root, i, j)


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)