Three implementations: binary index tree 7ms, segment tree array 14ms, segment tree 20ms, with comments
References:\n\nBinary Indexed Trees (BIT or Fenwick tree):\n\nhttps://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/\n\nSe
References:\n\nBinary Indexed Trees (BIT or Fenwick tree):\n\nhttps://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/\n\nSegment Tree | Set 1 (Sum of given range)\n\nhttp://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/\n\n\n\n    // Binary Index Tree - 7ms\n    // A BIT node : sum of all its left descendent and itself\n    \n    //* BIT[] as a binary tree:\n    //     *            ______________*\n    //     *            ______*\n    //     *            __*     __*\n    //     *            *   *   *   *\n    //     * indices: 0 1 2 3 4 5 6 7 8\n    \n    // Note NumArray query index i, and BIT index j has i + 1 = j; So be clear about it.\n    \n    \n    public class NumArray {\n        int bit[];\n        int arr[];\n        int n;\n        \n        public NumArray(int[] nums) {\n            n = nums.length;\n            arr = Arrays.copyOf(nums, n);\n            bit = new int[n + 1];\n            for (int i = 0; i < n; i++) updateBIT(i + 1, arr[i]);\n        }\n    \n        void update(int i, int val) {\n            int diff = val - arr[i];\n            arr[i] = val;\n            updateBIT(i + 1, diff);\n        }\n        \n        void updateBIT(int j, int diff) { \n            while (j <= n) {\n                bit[j] += diff;\n                j += j & -j;\n            }\n        }\n    \n        public int sumRange(int i, int j) {\n            return getSum(j + 1) - getSum(i);\n        }\n        \n        int getSum(int j) {\n            int sum = 0;\n            while (j > 0) {\n                sum += bit[j];\n                j -= j & -j;\n            }\n            return sum;\n        }\n    }\n    \n    \n    // Your NumArray object will be instantiated and called as such:\n    // NumArray numArray = new NumArray(nums);\n    // numArray.sumRange(0, 1);\n    // numArray.update(1, 10);\n    // numArray.sumRange(1, 2);\n    \n    \n    \n    /* Segment Tree - Array Implementation - 14ms\n    \n    // important key is for a range [l,r] of [0, n - 1], \n    // [l, r] is bound to segment index iSeg = 0;\n    // [l, mid] is bound to segment index iSeg*2 + 1;\n    // [mid+1, r] is bound to segment index iSeg*2 + 2;\n    // whenener [l,r] has l == r, it is a leaf and seg[iSeg] = arr[l];\n    \n    public class NumArray {\n        int[] seg, arr;\n        int nSeg, n;\n    \n        public NumArray(int[] nums) {\n            n = nums.length;\n            int rank = (int)Math.ceil(Math.log(n) / Math.log(2));\n            nSeg = (1 << rank + 1) - 1;\n            arr = Arrays.copyOf(nums, n);        //arr = new int[n];\n            seg = new int[nSeg];\n            makeTree(0, n - 1, 0);\n        }\n        \n        int makeTree(int l, int r, int iSeg) {\n            if (l > r) return 0;\n            if (l == r) {\n                seg[iSeg] = arr[l];\n                return seg[iSeg];\n            }\n            int mid = getMid(l, r);\n            seg[iSeg] = makeTree(l, mid, iSeg * 2 + 1)\n                    + makeTree(mid + 1, r, iSeg * 2 + 2);\n            return seg[iSeg];\n        }\n        \n        int getMid(int l, int r) {\n            return (l + r) / 2;\n        }\n    \n        void update(int i, int val) {\n            int diff = val - arr[i];\n            arr[i] = val;\n            updateTree(0, n - 1, i, diff, 0);\n        }\n        \n        void updateTree(int l, int r, int i, int diff, int iSeg) {\n            seg[iSeg] +=diff;\n            if (l == r) return;\n            int mid = getMid(l, r);\n            if (i > mid)\n                updateTree(mid + 1, r, i, diff, iSeg * 2 + 2);\n            else\n                updateTree(l, mid, i, diff, iSeg * 2 + 1);\n        }\n    \n        public int sumRange(int i, int j) {\n            return getSum(0, n - 1, i, j, 0);\n        }\n        \n        int getSum(int l, int r, int i, int j, int iSeg) {\n            if (l > j || r < i) return 0;\n            if (l >= i && r <= j) return seg[iSeg];\n            int mid = getMid(l, r);\n            return getSum(l, mid, i, j, iSeg * 2 + 1)     //search left chd\n            + getSum(mid + 1, r, i, j, iSeg * 2 + 2); //search right chd\n        }\n    }\n    */\n    \n    \n    /* Segment Tree - SegTreeNode Implementation - 20ms\n    \n    public class NumArray {\n        private class SegTreeNode {\n            int sum, l, r;\n            SegTreeNode left, right;\n            \n            public SegTreeNode(int sum1, int l1, int r1) {\n                sum = sum1; l = l1; r = r1;\n            }\n        }\n        \n        SegTreeNode root;\n    \n        public NumArray(int[] nums) {\n            root = makeTree(0, nums.length - 1, nums);\n        }\n        \n        private SegTreeNode makeTree(int l, int r, int[] nums) {\n            if (l > r) return null;\n            if (l == r) return new SegTreeNode(nums[l], l, l);\n            int mid = (l + r) / 2, sum = 0;\n            SegTreeNode left = makeTree(l, mid, nums);\n            SegTreeNode right = makeTree(mid + 1, r, nums);\n            if (left != null) sum += left.sum;\n            if (right != null) sum += right.sum;\n            SegTreeNode root = new SegTreeNode(sum, l, r);\n            root.left = left; \n            root.right = right;\n            return root;\n        }\n    \n        void update(int i, int val) {\n            updateTree(i, val, root);\n        }\n        \n        private void updateTree(int i, int val, SegTreeNode r) {\n            if (r.l == i && r.r == i) {\n                r.sum = val;\n                return;\n            }\n            SegTreeNode chd = (i > (r.l + r.r) / 2) ? r.right : r.left;\n            int oldsum = chd.sum;\n            updateTree(i, val, chd);\n            r.sum += chd.sum - oldsum;\n        }\n    \n        public int sumRange(int i, int j) {\n            return sumRange(i, j, root);\n        }\n        \n        private int sumRange(int i, int j, SegTreeNode r) {\n            if (r == null || i > j) return 0;\n            if (i == r.l && j == r.r) return r.sum;\n            \n            int mid = (r.l + r.r) / 2;\n            if (mid < i) \n                return sumRange(i, j, r.right);\n            else\n            if (mid >= j)\n                return sumRange(i, j, r.left);\n            else\n                return sumRange(i, mid, r.left) + sumRange(mid + 1, j, r.right);\n        }\n        \n        \n    }\n    \n    */
[]