区域检索-数组可修改

给定一个整数数组  nums，求出数组从索引 i 到 j  (i ≤ j) 范围内元素的总和，包含 i,  j 两点。

update(i, val) 函数可以通过将下标为 i 的数值更新为 val，从而对数列进行修改。

示例:

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9

update(1, 2)

sumRange(0, 2) -> 8

说明:

1. 数组仅可以在 update 函数下进行修改。
2. 你可以假设 update 函数与 sumRange 函数的调用次数是均匀分布的。

 1 class NumArray {
 2     int[] tree;
 3     int n;
 4     public NumArray(int[] nums){
 5         if(nums.length>0){
 6             n=nums.length;
 7             tree=new int[n*2];
 8             buildTree(nums);
 9         }
10     }
11     private void buildTree(int[] nums){
12         for(int i=n,j=0;i<2*n;i++,j++){
13             tree[i]=nums[j];
14         }
15         for(int i=n-1;i>0;--i){
16             tree[i]=tree[i*2]+tree[i*2+1];
17         }
18     }
19 
20     void update(int pos,int val){
21         pos+=n;
22         tree[pos]=val;
23         while(pos>0){
24             int left=pos;
25             int right=pos;
26             if(pos%2==0){
27                 right=pos+1;
28             }else{
29                 left=pos-1;
30             }
31             tree[pos/2]=tree[left]+tree[right];
32             pos/=2;
33         }
34     }
35 
36     public int sumRange(int l,int r){
37         l+=n;
38         r+=n;
39         int sum=0;
40         while(l<=r){
41             if((l%2)==1){
42                 sum+=tree[l];
43                 l++;
44             }
45             if((r%2)==0){
46                 sum+=tree[r];
47                 r--;
48             }
49             l/=2;
50             r/=2;
51         }
52         return sum;
53     }
54 }