Simple recursive Java solution
Here is my solution using a recursive class definition. O(n) constructor, O(log n) update and sumRange methods. I thought it was a little simpler than some of t
Here is my solution using a recursive class definition. O(n) constructor, O(log n) update and sumRange methods. I thought it was a little simpler than some of the other solutions. Each NumArray object of size n>1 stores a pointer to another NumArray object of size (n+1)/2 such that element i in the parent object stores the sum of the elements 2i and 2i+1 in the original object. Sums and updates are rapid because they just amount to climbing the tree.\n\n    public class NumArray {\n    \n        int n;\n        int[] raw;\n        NumArray parent;\n\n        public NumArray(int[] nums) {\n            n = nums.length;\n            raw = nums;\n            if (n>1) {\n                int[] parRaw = new int[(n+1)/2];\n                for (int i=0; i<n; i++) {\n                    parRaw[i/2]+=nums[i];\n                }\n                parent = new NumArray(parRaw);\n            }\n        }\n\n        public void update(int i, int val) {\n            if (n>1) {\n                parent.update(i/2, parent.get(i/2)-raw[i]+val);\n            }\n            raw[i]=val;\n        }\n    \n        public int get(int i) {\n            return raw[i];\n        }\n\n        public int sumRange(int i, int j) {\n            if (i>0) {\n                return sumRange(0,j) - sumRange(0,i-1);\n            } else if (j==0) {\n                return raw[0];\n            } else {\n                int sum = parent.sumRange(0,j/2);\n                if (j%2==0 && j+1<n) {\n                    sum -= raw[j+1];\n                }\n                return sum;\n            }\n        }\n    }
['Recursion', 'Java']