-
Notifications
You must be signed in to change notification settings - Fork 0
/
307Alternative.java
74 lines (71 loc) · 2.6 KB
/
307Alternative.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//https://leetcode.com/problems/range-sum-query-mutable/
public class NumArray {
int[] arr;
int size;
public NumArray(int[] nums) {
if(nums==null || nums.length==0) return;
size=nums.length;
int height=(int)(Math.ceil(Math.log(nums.length)/Math.log(2)));
arr=new int[2*(int)Math.pow(2,height)-1];
constructTree(nums,0,nums.length-1,0);
}
public int getMid(int start, int end){
return start+(end-start)/2;
}
public int constructTree(int[] nums, int start, int end, int index){
if(start==end){
arr[index]=nums[start];
return arr[index];
}
int mid=getMid(start,end);
arr[index]=constructTree(nums,start,mid,index*2+1)+constructTree(nums,mid+1,end,index*2+2);
return arr[index];
}
/*
public void updateTree(int i, int val, int start, int end, int index){
if(arr==null || i<start || i>end) return;
int mid=getMid(start,end);
if (i<=mid) updateTree(i, val, index*2+1, start, mid);
else updateTree(i, val, index*2+2, mid+1, end);
arr[index]=arr[index*2+1]+arr[index*2+2];
}
*/
void update(int i, int val) {
if(i<0 || i>=size) return;
// find arr index based on nums index
int start = 0; int end = size -1;
int arrIndex = 0;
while(start != end) {
int mid = getMid(start, end);
if( start<= i && i<= mid) {
end = mid;
arrIndex = arrIndex * 2 + 1;
} else {
start = mid + 1;
arrIndex = arrIndex * 2 + 2;
}
}
// update parent's arr value,
int diff = val - arr[arrIndex];
arr[arrIndex] = val;
while(arrIndex!=0) {
arrIndex = (arrIndex - 1)/2;
arr[arrIndex] += diff;
}
}
public int quaryRangeSum(int requiredLeft, int requiredRight, int start, int end, int index){
if(requiredLeft<=start && requiredRight>=end) return arr[index];
if(end<requiredLeft || start>requiredRight) return 0;
int mid=getMid(start,end);
return quaryRangeSum(requiredLeft,requiredRight,start,mid,2*index+1)+quaryRangeSum(requiredLeft,requiredRight,mid+1,end,2*index+2);
}
public int sumRange(int i, int j) {
if(arr == null || i<0 || j>=size || i>j) return -1;
return quaryRangeSum(i,j,0,size-1,0);
}
}
// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);