segment tree, binary indexed tree
performance\n- binary indexed tree (array impl)  1192ms\n- segmented tree (array impl)       1332ms\n- segmented tree                    1773ms\n\n\n1. Segmente
# performance\n- binary indexed tree (array impl)  `1192ms`\n- segmented tree (array impl)       `1332ms`\n- segmented tree                    `1773ms`\n\n\n1. Segmented Tree\n```\nclass NumArray:\n    def __init__(self, A: List[int]):\n        self.n = len(A)\n        self.t = SegTree(self.n)\n        for i in range(self.n):\n            self.t.set(i, A[i])\n\n    def update(self, i: int, v: int) -> None:\n        self.t.set(i, v)\n\n    def sumRange(self, l: int, r: int) -> int:\n        return self.t.get(l, r)\n\n\nclass SegTree:\n    def __init__(self, n):\n        self.root = self._init(0, n-1)\n\n    def _init(self, l, r):\n        node = Node(0, l, r)\n        if l==r:\n            return node\n        node.left = self._init(node.l, node.m)\n        node.right = self._init(node.m+1, node.r)\n        return node\n    \n    def get(self, l, r):\n        return self._get(self.root, l, r)\n\n    def _get(self, node, l, r):\n        # (l, r) <= (node.l, node.r)\n        if node.l == node.r:\n            return node.v\n        if node.l == l and node.r == r:  \n            # this makes get O(logn)\n            return node.v\n        if node.m+1 <= l:\n            return self._get(node.right, l, r)\n        if node.m >= r:\n            return self._get(node.left, l, r)\n        return self._get(node.left, l, node.m) + self._get(node.right, node.m+1, r)\n\n    def set(self, i, v):\n        self._set(self.root, i, v)\n\n    def _set(self, node, i, v):\n        if node.l == node.r:\n            dv = v - node.v\n            node.v = v\n            return dv\n        dv = 0\n        if node.m >= i:\n            dv = self._set(node.left, i, v)\n        else:\n            dv = self._set(node.right, i, v)\n        node.v += dv\n        return dv\n\n\nclass Node:\n    def __init__(self, v, l, r):\n        self.v = v\n        self.l = l\n        self.r = r\n        self.m = (l+r)>>1\n        self.left = None\n        self.right = None\n\n```\n\n2. Segmented Tree (1D array implementation)\n```\nclass NumArray1:\n    def __init__(self, A: List[int]):\n        self.n = len(A)\n        self.t = SegTree(self.n)\n        for i in range(self.n):\n            self.t.set(i, A[i])\n\n    def update(self, i: int, v: int) -> None:\n        self.t.set(i, v)\n\n    def sumRange(self, l: int, r: int) -> int:\n        return self.t.get(l, r)\n\n\nclass SegArr:\n    def __init__(self, A):\n        self.n = len(A)\n        self.t = [0]*n + A\n        for i in range(self.n-1, -1, -1):\n            self.t[i] += self.t[i<<1] + self.t[t<<1|1]\n    \n    def get(self, i, j):\n        i += self.n\n        j += self.n\n        res = 0\n        while i <= j:\n            if i & 1:\n                res += self.t[i]\n                i += 1\n            i >>= 1\n            if not (j & 1):\n                res += self.t[j]\n                j -= 1\n            j >>= 1\n        return res\n\n    def set(self, i, v):\n        i += self.n\n        dv = v - self.t[i]\n        while i > 0:\n            self.t[i] += dv\n            i >>= 1\n```\n\n3. [Binary Indexed Tree](https://leetcode.com/problems/range-sum-query-mutable/discuss/75730/148ms-Python-solution-Binary-Indexed-Tree) (list implementation) @kitt, @zjlvmiao\n```\nclass NumArray1:\n    def __init__(self, A: List[int]):\n        self.n = len(A)\n        self.b = Bit(self.n)\n        for i in range(self.n):\n            self.b.set(i+1, A[i])\n\n    def update(self, i: int, v: int) -> None:\n        b = self.b\n        v0 = b.get(i+1, i+1)\n        dv = v - v0\n        b.set(i+1, dv)\n\n    def sumRange(self, l: int, r: int) -> int:\n        return self.b.get(l+1, r+1)\n\n\nclass Bit:\n    # 1-based\n    # pointe update & range query\n    def __init__(self, n):\n        self.n = n\n        self.b = [0] * (n+1)\n\n    def get(self, l, r):\n        return self.pre(r) - self.pre(l-1)\n\n    def set(self, k, dv):\n        while k <= self.n:\n            self.b[k] += dv\n            k += k & -k\n    \n    def pre(self, k):\n        s = 0\n        while k > 0:\n            s += self.b[k]\n            k -= k & -k\n        return s\n```
['Binary Indexed Tree', 'Segment Tree']