Java 7ms Binary Index Tree solution
Fenwick tree (aka Binary indexed tree) is a data structure that maintains a sequence of elements, and is able to compute cumulative sum of any range of consecut
Fenwick tree (aka Binary indexed tree) is a data structure that maintains a sequence of elements, and is able to compute cumulative sum of any range of consecutive elements in `O(log n)` time. Changing value of any single element needs `O(log n)` time as well.\n\nThe structure is space-efficient in the sense that it needs the same amount of storage as just a simple array of n elements.\n\nThe basic rule that the structure works on is that, just like a number can be represented as a sum of some powers of two, so can a cumulative sum be represented as a sum of some partial cumulative sums .\n\nEvery index in the cumulative sum array, say `i`, is responsible for the cumulative sum from the index `i` to `(i - (1<<r) + 1)`, where r represents the last 1 bit set int the index `i`.\n\n----From Algorithmist "[Fenwick tree][1]"\n\n    public class NumArray {\n        int[] tree;\n        int[] nums;\n        int size;\n        public NumArray(int[] nums) {\n            this.size = nums.length;\n            this.nums = new int[size];\n            this.tree = new int[size];\n            for (int i = 0; i < size; ++i)\n                update(i, nums[i]);\n        }\n        public void update(int i, int val) {\n            int delta = val - nums[i];\n            nums[i] = val;\n            for (; i < size; i |= i + 1)\n                tree[i] += delta;\n        }\n        public int sumRange(int i, int j) {\n            return sum(j) - sum(i - 1);\n        }\n        public int sum(int ind) {\n            int ans = 0;\n            while (ind >= 0) {\n                ans += tree[ind];\n                ind &= ind + 1;\n                ind--;\n            }\n            return ans;\n        }\n    }\n    // Runtime: 7ms\n\n\n  [1]: http://www.algorithmist.com/index.php/Fenwick_tree
['Binary Tree', 'Java']