[Java] Binary Indexed Tree / Fenwick Tree - O(logn)
The upvotest BIT post has a clear explanation.\nI just optimized it based on the default BIT.\njava\nclass NumArray {\n    int[] bit;\n    int[] nums;\n    publ
The upvotest [BIT post](https://leetcode.com/problems/range-sum-query-mutable/discuss/75753/Java-using-Binary-Indexed-Tree-with-clear-explanation) has a clear explanation.\nI just optimized it based on the default BIT.\n```java\nclass NumArray {\n    int[] bit;\n    int[] nums;\n    public NumArray(int[] nums) {\n        this.nums = new int[nums.length];\n        bit = new int[nums.length + 1];\n        for (int i = 0; i < nums.length; i++) {\n            update(i, nums[i]);\n        }\n    }\n\n    public void update(int i, int val) {\n        int diff = val - nums[i];\n        nums[i] = val;\n        i++;\n        while (i < bit.length) {\n            bit[i] += diff;\n            i += i & -i;\n        }\n    }\n\n    public int query(int i) {\n        i++;\n        int res = 0;\n        while (i > 0) {\n            res += bit[i];\n            i -= i & -i;\n        }\n        return res;\n    }\n\n    public int sumRange(int i, int j) {\n        return query(j) - query(i - 1);\n    }\n}\n\n/**\n * Your NumArray object will be instantiated and called as such:\n * NumArray obj = new NumArray(nums);\n * obj.update(i,val);\n * int param_2 = obj.sumRange(i,j);\n */\n```
['Tree', 'Binary Indexed Tree', 'Java']