Java Segmeng Tree Solution with Explaination
First build a Segment Tree, implements build, update and range operations.  \nThe tree holds the indices of the data array, tree node hold the indices and sum o
First build a Segment Tree, implements build, update and range operations.  \nThe tree holds the indices of the data array, tree node hold the indices and sum of this range.  \nFor build operation,  divide and conqure, split range into start~mid and mid+1~end, calculate sum recursively.  this operates N/2 + N/4 + N/8 + ... + N/N = N-1 times to build a binary segement tree.  leaf node has same start and end index.  \nFor update operation, search node as search in binary search tree, update sum values in the path, time complexity is O(lgN).  \nFor range operation, divide and conqure with 4 conditions:  \n1, range meet the node, return sum  \n2, range meet the node.left(end <= node.mid), operate on node.left recursively  \n3, range meet the node.right( start > node.mid), operate on node.right recursively  \n4, range span node.left and node.right, operate sum(node.left, start, mid) + sum(node.right, mid+1, right) recursively  \n    \n    public class NumArray {\n        public class TreeNode {\n            int start = 0;\n            int end = 0;\n            int sum = 0;\n    \n            TreeNode left = null;\n            TreeNode right = null;\n        }\n    \n        private TreeNode root = null;\n        private int[] data = null;\n    \n        public void init(int[] data) {\n            if (data == null || data.length == 0) return;\n            this.data = data;\n            this.root = build(0, data.length - 1);\n        }\n    \n        private TreeNode build(int start, int end) {\n            TreeNode node = new TreeNode();\n            node.start = start;\n            node.end = end;\n    \n            if (start == end) {\n                node.sum = data[start];\n                return node;\n            }\n    \n            int mid = start + (end - start) / 2;\n            node.left = build(start, mid);\n            node.right = build(mid + 1, end);\n    \n            node.sum = node.left.sum + node.right.sum;\n            return node;\n        }\n    \n        private void update(TreeNode node, int index, int num) {\n            if (node == null) return;\n            if (node.start == node.end) {\n                node.sum = num;\n                return;\n            }\n            int mid = node.start + (node.end - node.start) / 2;\n            if (index <= mid) {\n                update(node.left, index, num);\n            } else {\n                update(node.right, index, num);\n            }\n            node.sum = node.left.sum + node.right.sum;\n        }\n    \n        private int getSum(TreeNode node, int start, int end) {\n             if (start < node.start || end > node.end) {\n                return -1;\n            }\n    \n            if (start == node.start && end == node.end) {\n                return node.sum;\n            }\n    \n            int mid = node.start + (node.end - node.start) / 2;\n    \n            if (start > mid) {\n                return getSum(node.right, start, end);\n            }\n            if (end <= mid) {\n                return getSum(node.left, start, end);\n            }\n            \n            return getSum(node.left, start, mid) + getSum(node.right, mid+1, end);\n        }\n    \n        public int getSum(int start, int end) {\n            return getSum(root, start, end);\n        }\n        \n        public NumArray(int[] nums) {\n           init(nums);\n        }\n    \n        void update(int i, int val) {\n            update(root, i, val);\n        }\n    \n        public int sumRange(int i, int j) {\n            return getSum(i, j);\n        }\n    }
[]