-
Notifications
You must be signed in to change notification settings - Fork 1.3k
/
Node.java
139 lines (104 loc) · 3.82 KB
/
Node.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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/**
* Segment Trees are an extremely useful data structure when dealing with ranges or intervals. They
* take O(n) time and space to construct, but they can do range updates or queries in O(log(n))
* time. This data structure is quite flexible; although the code below supports minimum and sum
* queries, these could be modified to perform other types of queries. This implementation uses lazy
* propagation (which allows for O(log(n)) range updates instead of O(n)). It should also be noted
* that this implementation could easily be modified to support coordinate compression (you should
* only have to change a few lines in the constructor).
*
* @author Micah Stairs
*/
package com.williamfiset.datastructures.segmenttree;
public class Node {
static final int INF = Integer.MAX_VALUE;
Node left, right;
int minPos, maxPos, min = 0, sum = 0, lazy = 0;
public Node(int[] values) {
if (values == null) throw new IllegalArgumentException("Null input to segment tree.");
buildTree(0, values.length);
for (int i = 0; i < values.length; i++) {
update(i, i + 1, values[i]);
}
}
public Node(int sz) {
buildTree(0, sz);
}
private Node(int l, int r) {
buildTree(l, r);
}
// Recursive method that builds the segment tree
private void buildTree(int l, int r) {
if (l < 0 || r < 0 || r < l)
throw new IllegalArgumentException("Illegal range: (" + l + "," + r + ")");
minPos = l;
maxPos = r;
// Reached leaf
if (l == r - 1) {
left = right = null;
// Add children
} else {
int mid = (l + r) / 2;
left = new Node(l, mid);
right = new Node(mid, r);
}
}
// Adjust all values in the interval [l, r) by a particular amount
public void update(int l, int r, int change) {
// Do lazy updates to children
propagate();
// Node's range fits inside query range
if (l <= minPos && maxPos <= r) {
sum += change * (maxPos - minPos);
min += change;
// Lazily propagate update to children
if (left != null) left.lazy += change;
if (right != null) right.lazy += change;
// Ranges do not overlap
} else if (r <= minPos || l >= maxPos) {
// Do nothing
// Ranges partially overlap
} else {
if (left != null) left.update(l, r, change);
if (right != null) right.update(l, r, change);
sum = (left == null ? 0 : left.sum) + (right == null ? 0 : right.sum);
min = Math.min((left == null ? INF : left.min), (right == null ? INF : right.min));
}
}
// Get the sum in the interval [l, r)
public int sum(int l, int r) {
// Do lazy updates to children
propagate();
// Node's range fits inside query range
if (l <= minPos && maxPos <= r) return sum;
// Ranges do not overlap
else if (r <= minPos || l >= maxPos) return 0;
// Ranges partially overlap
else return (left == null ? 0 : left.sum(l, r)) + (right == null ? 0 : right.sum(l, r));
}
// Get the minimum value in the interval [l, r)
public int min(int l, int r) {
// Do lazy updates to children
propagate();
// Node's range fits inside query range
if (l <= minPos && maxPos <= r) return min;
// Ranges do not overlap
else if (r <= minPos || l >= maxPos) return INF;
// Ranges partially overlap
else
return Math.min(
(left == null ? INF : left.min(l, r)), (right == null ? INF : right.min(l, r)));
}
// Does any updates to this node that haven't been done yet, and lazily updates its children
// NOTE: This method must be called before updating or accessing a node
private void propagate() {
if (lazy != 0) {
sum += lazy * (maxPos - minPos);
min += lazy;
// Lazily propagate updates to children
if (left != null) left.lazy += lazy;
if (right != null) right.lazy += lazy;
lazy = 0;
}
}
}