-
Notifications
You must be signed in to change notification settings - Fork 2
/
RangeSumQueryMutable.java
79 lines (67 loc) · 2.21 KB
/
RangeSumQueryMutable.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
75
76
77
78
79
package src.java.medium.array;
class NumArray {
class Node {
int start, end;
int val;
Node left, right;
Node(int val) {
this.val = val;
}
Node(int val, int start, int end) {
this.val = val;
this.start = start;
this.end = end;
}
}
class SegmentTree {
Node root;
SegmentTree(int[] nums) {
root = build(nums, 0, nums.length-1);
}
private Node build(int[] nums, int start, int end) {
if (start > end) return null;
if (start == end) return new Node(nums[start], start, end);
int mid = start + (end - start)/2;
Node left = build(nums, start, mid);
Node right = build(nums, mid+1, end);
Node node = new Node(left.val+right.val, start, end);
node.left = left;
node.right = right;
return node;
}
void update(int i, int val, Node node) {
if (node.start==i && node.end==i) {
node.val = val;
return;
}
int mid = node.start + (node.end - node.start)/2;
if (i <= mid) update(i, val, node.left);
else update(i, val, node.right);
node.val = node.left.val + node.right.val;
}
int sumRange(int i, int j, Node node) {
if (node.start == i && node.end == j) return node.val;
int mid = node.start + (node.end - node.start)/2;
if (mid >= j) return sumRange(i, j, node.left);
else if (mid < i) return sumRange(i, j, node.right);
else {
return sumRange(i, mid, node.left) + sumRange(mid+1, j, node.right);
}
}
Node getRoot() {
return this.root;
}
}
SegmentTree st;
Node root;
public NumArray(int[] nums) {
st = new SegmentTree(nums);
root = st.getRoot();
}
public void update(int i, int val) {
st.update(i, val, root);
}
public int sumRange(int i, int j) {
return st.sumRange(i, j, root);
}
}