-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathP_327.java
More file actions
86 lines (78 loc) · 2.51 KB
/
Copy pathP_327.java
File metadata and controls
86 lines (78 loc) · 2.51 KB
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
80
81
82
83
84
85
86
package leetcode.hard;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class P_327 {
private static class SegTree {
int leftMost, rightMost;
SegTree left, right;
int sum;
SegTree(int leftMost, int rightMost, int[] arr) {
this.leftMost = leftMost;
this.rightMost = rightMost;
if (leftMost == rightMost) {
sum = arr[leftMost];
} else {
final int mid = leftMost + rightMost >>> 1;
left = new SegTree(leftMost, mid, arr);
right = new SegTree(mid + 1, rightMost, arr);
recalc();
}
}
private void recalc() {
if (leftMost == rightMost) {
return;
}
sum = left.sum + right.sum;
}
private int query(int l, int r) {
if (r < leftMost || l > rightMost) {
return 0;
}
if (l <= leftMost && rightMost <= r) {
return sum;
}
return left.query(l, r) + right.query(l, r);
}
private void update(int idx, int val) {
if (leftMost == rightMost) {
sum += val;
} else {
final int mid = leftMost + rightMost >>> 1;
if (idx <= mid) {
left.update(idx, val);
} else {
right.update(idx, val);
}
recalc();
}
}
}
public int countRangeSum(int[] nums, int lower, int upper) {
int idx = 0;
int res = 0;
final int n = nums.length;
final long[] sum = new long[n + 1];
final long[] range = new long[3 * sum.length];
final SegTree st = new SegTree(0, range.length - 1, new int[range.length]);
for (int i = 0; i <= n; i++) {
sum[i] = i == 0 ? 0 : (sum[i - 1] + nums[i - 1]);
range[idx++] = sum[i];
range[idx++] = lower + sum[i];
range[idx++] = upper + sum[i];
}
Arrays.sort(range);
final Map<Long, Integer> map = new HashMap<>();
for (int i = 0; i < range.length; i++) {
map.put(range[i], i);
}
for (long val : sum) {
st.update(map.get(val), 1);
}
for (long val : sum) {
st.update(map.get(val), -1);
res += st.query(map.get(val + lower), map.get(val + upper));
}
return res;
}
}