Java Binary Indexed Tree
Both update and getSum Complexity would be O(logn).\n\nBasic idea is we take the array as a tree when we initialize it where child node index equals to parent n
Both update and getSum Complexity would be O(logn).\n\nBasic idea is we take the array as a tree when we initialize it where child node index equals to parent node index's last set bit - 1. When we get sum we take it as the tree where child node index equals to parent node index's last set bit + 1. \n\nDespite this, the general idea is similar to Range Sum Query I.\n\nFor detail of Binary Indexed Tree you can take a look at this link http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/\n\n    public class NumArray {\n    \tint[] tree;\n    \tint[] nums;\n    \tint size;\n        public NumArray(int[] nums) {\n            this.size = nums.length;\n            this.tree = new int[size + 1];\n            this.nums = new int[size];\n            this.nums = nums;\n            for(int i = 0; i < size; i++){\n            \tupdateTree(i, nums[i]);\n            }\n        }\n    \n        public void updateTree(int i, int val) {\n            i = i + 1;\n            while(i <= size){\n            \ttree[i] += val;\n            \ti += i & (-i); // the last set bit/ Two's complement\n            }\n        }\n        \n        public void update(int i, int val){\n            updateTree(i, val - nums[i]);\n            nums[i] = val;\n        }\n    \n        private int getSum(int i){\n        \tint sum = 0;\n        \ti = i + 1;\n        \twhile(i > 0){\n        \t\tsum += tree[i];\n        \t\ti -= i & (-i);// Another tree, go to the ancestor\n        \t}\n        \treturn sum;\n        }\n    \n        public int sumRange(int i, int j){\n            if(i == 0) return getSum(j);\n         \treturn getSum(j) - getSum(i - 1);\n        }\n    \n      \n    }
['Binary Tree']