[C++ / Python 3] Fenwick Tree
Python\n\nclass NumArray:\n    def getsum(self, i): \n        ans = 0\n        i += 1\n        while i > 0: \n            ans += self.BITTree[i] \n            i
**Python**\n```\nclass NumArray:\n    def getsum(self, i): \n        ans = 0\n        i += 1\n        while i > 0: \n            ans += self.BITTree[i] \n            i -= i & (-i) \n        return ans     \n    \n    def updatebit(self, i, v): \n        i += 1\n        while i <= self.n: \n            self.BITTree[i] += v \n            i += i & (-i) \n\n    def construct(self, arr): \n        for i in range(self.n): \n            self.updatebit(i, arr[i]) \n        return \n    \n    def __init__(self, nums: List[int]):\n        self.nums = nums\n        self.n = len(self.nums) \n        self.BITTree = [0] * (self.n + 1)         \n        self.construct(nums)         \n        \n    def update(self, i: int, val: int) -> None:\n        diff = val - self.nums[i]\n        self.updatebit(i, diff)\n        self.nums[i] = val\n        return\n\n    def sumRange(self, i: int, j: int) -> int:\n        return self.getsum(j) - self.getsum(i - 1)\n```\n\n**C++**\n```\nclass BITTree{\n\tpublic:\n\tvector<int> cnt;\n\tBITTree(int n): cnt(n+1, 0){\n\t}\n\n\tvoid update(int i, int delt){\n\t\twhile(i < cnt.size()){\n\t\t\tcnt[i] += delt;\n\t\t\ti += i & (-i);\n\t\t}\n\t}\n\n\tint construct(int a){\n\t\tint sum = 0;\n\t\twhile (a > 0){\n\t\t\tsum += cnt[a];\n\t\t\ta -= a & (-a);\n\t\t}\n\t\treturn sum;\n\t}\n};\n\n\nclass NumArray {\npublic:\n\tBITTree Tree;\n\tvector<int> num;\n\tNumArray(vector<int>& nums): Tree(nums.size()){\n\t\tint n = nums.size();\n\t\tnum = nums;\n\n\t\tfor(int i = 0; i < n; i ++){\n\t\t\tTree.update(i + 1, num[i]);\n\t\t}\n\t}\n\n\tvoid update(int i, int val) {\n\t\tTree.update(i + 1, val - num[i]);\n\t\tnum[i] = val;\n\t}\n\n\tint sumRange(int i, int j) {\n\t\treturn Tree.construct(j + 1) - Tree.construct(i);\n\t}\n};\n```
[]