[Python] Fenwick Tree (BIT) AND Segment Tree | O(nlogn) | Short & Concise
Nothing special, just a fenwick tree. \n\nNote on Fenwick tree implementation:\n- Use 1-indexed array to perform bit manipulation\n- i&-i to extract the last la
Nothing special, just a fenwick tree. \n\nNote on Fenwick tree implementation:\n- Use 1-indexed array to perform bit manipulation\n- i&-i to extract the last last bit. \n- range(i, j) = query(j) - query(i-1) \n- query(i) returns the prefix sum until i\n\nThis is a very smart data structure, less versatile than segment tree but easier to implement.\n\n```\nclass NumArray:\n    def __init__(self, nums: List[int]):\n        self.nums = nums\n        self.BIT = [0] * (len(self.nums)+1)\n        for i in range(len(self.nums)):\n            self.update(i, nums[i], True)\n            \n    def update(self, i: int, val: int, init=False) -> None:\n        if not init:\n            # only update the difference  \n            val, self.nums[i] = val - self.nums[i], val\n        i += 1\n        while i < len(self.BIT):\n            self.BIT[i] += val\n            i += (i&-i)\n                        \n    def sumRange(self, i: int, j: int) -> int:\n        return self.query(j) - self.query(i-1)\n        \n    def query(self, i):\n        i += 1\n        ans = 0\n        while i > 0:\n            ans += self.BIT[i]\n            i -= (i&-i)\n        return ans\n```\nSegment Tree is way easier to understand since it doesn\'t contain bit manipulation (which might be hard to understand). However, it is harder to implement as you can tell by its length. However, it is more verstaile since each node and store more informations.\n```\nclass Node:\n    def __init__(self, l, r, val, left, right):\n        self.l = l\n        self.r = r\n        self.val = val\n        self.left = left\n        self.right = right\n        \nclass NumArray:\n    def __init__(self, nums: List[int]):\n        self.nums = nums\n        if not nums:\n            self.root = None\n        else:\n            self.root = self.construct(0, len(nums)-1)\n    \n    def construct(self, l, r):\n        if l == r:\n            return Node(l, r, self.nums[l], None, None)\n        mid = (l+r)//2\n        left = self.construct(l, mid)\n        right = self.construct(mid+1, r)\n        return Node(l, r, left.val+right.val, left, right)\n            \n    def update(self, i: int, val: int) -> None:\n        self.stUpdate(self.root, i, val)\n        \n    def stUpdate(self, node, i, val):\n        if node.l == node.r == i:\n            node.val = val\n            return\n        mid = (node.l+node.r)//2\n        if i <= mid:\n            self.stUpdate(node.left, i, val)\n        else:\n            self.stUpdate(node.right, i, val)\n        node.val = node.left.val + node.right.val\n                        \n    def sumRange(self, i: int, j: int) -> int:\n        return self.stQuery(self.root, i, j)\n        \n    def stQuery(self, node, i, j):\n        if node.l == i and node.r == j:\n            return node.val\n        mid = (node.l+node.r)//2\n        if j <= mid:\n            return self.stQuery(node.left, i, j)\n        elif i > mid:\n            return self.stQuery(node.right, i, j)\n        else:\n            return self.stQuery(node.left, i, mid) + self.stQuery(node.right, mid+1, j)\n```
['Tree', 'Binary Indexed Tree', 'Python']