MEDIUM/src/medium/RangeSumQueryMutable.java

fishercoder1534 · fishercoder1534 · commit acb9cf4d58c1 · 2016-09-24T13:14:12.000-07:00
diff --git a/MEDIUM/src/medium/RangeSumQueryMutable.java b/MEDIUM/src/medium/RangeSumQueryMutable.java
@@ -0,0 +1,93 @@
+package medium;
+
+public class RangeSumQueryMutable {
+        
+    public static void main(String...strings){
+//        int[] nums = new int[]{1,3,5};
+        
+        int[] nums = new int[]{7,2,7,2,0};
+        NumArray test = new NumArray(nums);
+        test.update(4,6);
+        test.update(0,2);
+        test.update(0,9);
+    }
+}
+
+class NumArray {
+    class SegmentTreeNode{
+        SegmentTreeNode left;
+        SegmentTreeNode right;
+        int start;
+        int end;
+        int sum;
+        
+        public SegmentTreeNode(int start, int end){
+            this.start = start;
+            this.end = end;
+            this.left = null;
+            this.right = null;
+            this.sum = 0;
+        }
+    }
+    
+    private SegmentTreeNode root = null;
+
+    public NumArray(int[] nums) {
+        root = buildSegmentTree(nums, 0, nums.length-1);
+    }
+    
+    SegmentTreeNode buildSegmentTree(int[] nums, int start, int end){
+        if(start > end){
+            return null;
+        } else {
+            SegmentTreeNode root = new SegmentTreeNode(start, end);
+            if(start == end){
+                root.sum = nums[start];
+            } else {
+                int mid = start + (end-start)/2;
+                root.left = buildSegmentTree(nums, start, mid);
+                root.right = buildSegmentTree(nums, mid+1, end);
+                root.sum = root.left.sum + root.right.sum;
+            }
+            return root;
+        }
+    }
+
+    void update(int i, int val) {
+        update(root, i, val);
+    }
+    
+    void update(SegmentTreeNode root, int pos, int val){
+        if(root.start == root.end){
+            root.sum = val;
+        } else {
+            int mid = root.start + (root.end - root.start)/2;
+            if(pos <= mid){
+                update(root.left, pos, val);
+            } else {
+                update(root.right, pos, val);
+            }
+            root.sum = root.left.sum + root.right.sum;
+        }
+    }
+
+    public int sumRange(int i, int j) {
+        return sumRange(root, i, j);
+    }
+    
+    int sumRange(SegmentTreeNode root, int start, int end){
+        if(root.end == end && root.start == start){
+            return root.sum;
+        } else {
+            int mid = root.start + (root.end-root.start)/2;
+            if(end <= mid){
+                return sumRange(root.left, start, end);
+            } else if(start >= mid+1){
+                return sumRange(root.right, start, end);
+            } else {
+                return sumRange(root.right, mid+1, end) + sumRange(root.left, start, mid);
+            }
+        }
+    }
+}
+
