|
1 | 1 | packageg0301_0400.s0307_range_sum_query_mutable; |
2 | 2 |
|
3 | 3 | // #Medium #Array #Design #Segment_Tree #Binary_Indexed_Tree |
4 | | -// #2022_07_07_Time_99_ms_(88.96%)_Space_138.9_MB_(5.17%) |
| 4 | +// #2023_03_31_Time_92_ms_(90.27%)_Space_75.3_MB_(16.68%) |
5 | 5 |
|
6 | 6 | publicclassNumArray { |
| 7 | +privateint[]tree; |
7 | 8 | privateint[]nums; |
8 | | -privateintsum; |
9 | 9 |
|
10 | 10 | publicNumArray(int[]nums) { |
| 11 | +tree =newint[nums.length +1]; |
11 | 12 | this.nums =nums; |
12 | | -sum =0; |
13 | | -for (intnum :nums) { |
14 | | -sum +=num; |
| 13 | +// copy the array into the tree |
| 14 | +System.arraycopy(nums,0,tree,1,nums.length); |
| 15 | +for (inti =1;i <tree.length;i++) { |
| 16 | +intparent =i + (i & -i); |
| 17 | +if (parent <tree.length) { |
| 18 | +tree[parent] +=tree[i]; |
| 19 | + } |
15 | 20 | } |
16 | 21 | } |
17 | 22 |
|
18 | 23 | publicvoidupdate(intindex,intval) { |
19 | | -sum -=nums[index] -val; |
| 24 | +intcurrValue=nums[index]; |
20 | 25 | nums[index] =val; |
| 26 | +index++; |
| 27 | +while (index <tree.length) { |
| 28 | +tree[index] =tree[index] -currValue +val; |
| 29 | +index =index + (index & -index); |
| 30 | + } |
21 | 31 | } |
22 | 32 |
|
23 | | -publicintsumRange(intleft,intright) { |
24 | | -intsumRange =0; |
25 | | -if ((right -left) <nums.length /2) { |
26 | | -// Array to sum is less than half |
27 | | -for (inti =left;i <=right;i++) { |
28 | | -sumRange +=nums[i]; |
29 | | - } |
30 | | - }else { |
31 | | -// Array to sum is more than half |
32 | | -// Better to take total sum and substract the numbers not in range |
33 | | -sumRange =sum; |
34 | | -for (inti =0;i <left;i++) { |
35 | | -sumRange -=nums[i]; |
36 | | - } |
37 | | -for (inti =right +1;i <nums.length;i++) { |
38 | | -sumRange -=nums[i]; |
39 | | - } |
| 33 | +privateintsum(inti) { |
| 34 | +intsum =0; |
| 35 | +while (i >0) { |
| 36 | +sum +=tree[i]; |
| 37 | +i -= (i & -i); |
40 | 38 | } |
41 | | -returnsumRange; |
| 39 | +returnsum; |
| 40 | + } |
| 41 | + |
| 42 | +publicintsumRange(intleft,intright) { |
| 43 | +returnsum(right +1) -sum(left); |
42 | 44 | } |
43 | 45 | } |
| 46 | + |
| 47 | +/* |
| 48 | + * Your NumArray object will be instantiated and called as such: |
| 49 | + * NumArray obj = new NumArray(nums); |
| 50 | + * obj.update(index,val); |
| 51 | + * int param_2 = obj.sumRange(left,right); |
| 52 | + */ |