-
-
Notifications
You must be signed in to change notification settings - Fork 31
Expand file tree
/
Copy pathSegment Tree Modify.java
More file actions
executable file
·145 lines (123 loc) · 4.5 KB
/
Copy pathSegment Tree Modify.java
File metadata and controls
executable file
·145 lines (123 loc) · 4.5 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
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
140
141
142
143
144
145
M
1527895515
tags: Segment Tree, Binary Tree, Divide and Conquer, DFS, Lint
给一个segmentTree, node里面存max. 写一个modify function: modify(node, index, value).
#### Segment Tree, Divide and Conquer
- Recursively 在segment tree里面找index, update it with value.
- 每个iteration，很可能（要么左手，要么右手）max就变了。所以每次都left.max and right.max compare一下
- 最后轮回到头顶，头顶一下包括头顶，就全部都是max了
```
/*
For a Maximum Segment Tree, which each node has an extra value max
to store the maximum value in this node's interval.
Implement a modify function with three parameter root, index and value
to change the node's value with [start, end] = [index, index] to the new given value.
Make sure after this change, every node in segment tree still has the max attribute with the correct value.
Do Segment Tree build, Query problems first
Example
For segment tree:
[1, 4, max=3]
/ \
[1, 2, max=2] [3, 4, max=3]
/ \ / \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=3]
if call modify(root, 2, 4), we can get:
[1, 4, max=4]
/ \
[1, 2, max=4] [3, 4, max=3]
/ \ / \
[1, 1, max=2], [2, 2, max=4], [3, 3, max=0], [4, 4, max=3]
or call modify(root, 4, 0), we can get:
[1, 4, max=2]
/ \
[1, 2, max=2] [3, 4, max=0]
/ \ / \
[1, 1, max=2], [2, 2, max=1], [3, 3, max=0], [4, 4, max=0]
Note
We suggest you finish problem Segment Tree Build and Segment Tree Query first.
Challenge
Do it in O(h) time, h is the height of the segment tree.
Tags Expand
LintCode Copyright Binary Tree Segment Tree
*/
/*
Change value at leaf, and update all the parents' max till root.
1. find the target node recursively
compare target against root.start, root.end.
choose dfs
compare && update
2. in each dfs, update max
end case: start/end == target index, update node value, then return.
*/
class SegmentTreeNode {
SegmentTreeNode left, right;
int start, end, max;
public SegmentTreeNode(int start, int end, int max) {
this.start = start;
this.end = end;
this.max = max;
}
}
class Solution {
public void modify(SegmentTreeNode root, int target, int value) {
// check edge case
if (root == null) {
return;
}
if (root.start == root.end && root.start == target) {
root.max = value;
return;
}
// dfs: find desired target direction, call modify()
if (target <= root.left.end) {
modify(root.left, target, value);
} else if (target >= root.right.start){
modify(root.right, target, value);
} else {
return;
}
// update max
root.max = Math.max(root.left.max, root.right.max);
}
}
/*
Thought:
Renew index x with new value, and update the max value alone the way.
1. Use segmenttree property to find that leaf, which is node.start == node.end == index.
2. Along the way, whenever going to one segment/interval, compare left.max and right.max again, and update max.
*/
/**
* Definition of SegmentTreeNode:
* public class SegmentTreeNode {
* public int start, end, max;
* public SegmentTreeNode left, right;
* public SegmentTreeNode(int start, int end, int max) {
* this.start = start;
* this.end = end;
* this.max = max
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
*@param root, index, value: The root of segment tree and
*@ change the node's value with [index, index] to the new given value
*@return: void
*/
public void modify(SegmentTreeNode root, int index, int value) {
if (root.start == root.end && root.start == index) {
root.max = value;
return;
}
//Divide and seawrch
int mid = (root.start + root.end)/2;
if (index <= mid) {
modify(root.left, index, value);
} else {
modify(root.right, index, value);
}
root.max = Math.max(root.left.max, root.right.max);
}
}
```