Share my Java Binary Indexed Tree Solution
In the following solution, initializing the binary indexed tree takes O(nlogn) time, both update() and getSum() take O(logn) time. The arr[] is used to keep a b
In the following solution, initializing the binary indexed tree takes `O(nlogn)` time, both `update()` and `getSum()` take `O(logn)` time. The `arr[]` is used to keep a backup of the `nums[]` so that we know the difference of the updated element and use that to update the binary indexed tree.\n\nFor detailed explanation, please read this [article][1].\n\n    public class NumArray {\n      int[] arr;    // stores nums[]\n      int[] BITree; // binary indexed tree\n    \n      public NumArray(int[] nums) {\n        int n = nums.length;\n        arr = new int[n];\n        BITree = new int[n + 1];\n        \n        for (int i = 0; i < n; i++) {\n          update(i, nums[i]); // init BITree[]\n          arr[i] = nums[i];   // init arr[]\n        }\n      }\n    \n      void update(int i, int val) {\n        int diff = val - arr[i]; // get the diff\n        arr[i] = val;            // update arr[]\n        \n        i++;\n        while (i <= arr.length) {\n          BITree[i] += diff; // update BITree[]\n          i += i & (-i);     // update index to that of parent\n        }\n      }\n      \n      int getSum(int i) {\n        int sum = 0;\n        \n        i++;\n        while (i > 0) {\n          sum += BITree[i]; // accumulate the sum\n          i -= i & (-i);    // move index to parent node\n        }\n        return sum;\n      }\n    \n      public int sumRange(int i, int j) {\n        return getSum(j) - getSum(i - 1);\n      }\n    }\n\n\n  [1]: http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
['Binary Tree', 'Java']