leetcode
    image.png
    image.png

    1. class NumArray {
    2.     class TreeNode{
    3.         int sum;
    4.         int start,end;
    5.         TreeNode left,right;
    6.         public TreeNode(int s,int e){
    7.             left = null;
    8.             right = null;
    9.             start = s;
    10.             end = e;
    11.         }
    12.     }
    13.     TreeNode root = null;
    14.     private TreeNode buildTree(int[] nums,int start,int end){
    15.         if(start > end){
    16.             return null;
    17.         }
    18.         TreeNode res = new TreeNode(start,end);
    19.         if(start == end){
    20.             res.sum = nums[start];
    21.         }else{
    22.             int mid = start + (end - start)/2;
    23.             res.left = buildTree(nums,start,mid);
    24.             res.right = buildTree(nums,mid+1,end); 
    25.             res.sum = res.left.sum + res.right.sum;
    26.         }
    27.         return res;
    28.     }
    29.     public NumArray(int[] nums) {
    30.         root = buildTree(nums,0,nums.length - 1);
    31.     }
    33.     private void update(TreeNode root,int i,int val){
    34.         if(root.start == root.end){
    35.             root.sum = val;
    36.         }else{
    37.             int mid = root.start + (root.end - root.start)/2;
    38.             if(i<=mid){
    39.                 update(root.left,i,val);
    40.             }else{
    41.                 update(root.right,i,val);
    42.             }
    43.             root.sum = root.left.sum + root.right.sum;
    44.         }
    45.     }
    47.     public void update(int index, int val) {
    48.         update(root,index,val);
    49.     }
    51.     private int query(TreeNode root,int i,int j){
    52.         if(root.start == i&&root.end == j){
    53.             return root.sum;
    54.         }else{
    55.             int mid = root.start + (root.end - root.start)/2;
    56.             if(j<=mid){
    57.                 return query(root.left,i,j);
    58.             }else if(i>=mid+1){
    59.                 return query(root.right,i,j);
    60.             }else{
    61.                 return query(root.left,i,mid) + query(root.right,mid+1,j);
    62.             }
    63.         }
    64.     }
    65.     public int sumRange(int left, int right) {
    66.         return query(root,left,right);
    67.     }
    68. }
    70. /**
    71.  * Your NumArray object will be instantiated and called as such:
    72.  * NumArray obj = new NumArray(nums);
    73.  * obj.update(index,val);
    74.  * int param_2 = obj.sumRange(left,right);
    75.  */