Lintcode - Segment Tree Modify - 雯雯熊孩子 - 博客频道 - CSDN.NET
Read full article from Lintcode - Segment Tree Modify - 雯雯熊孩子 - 博客频道 - CSDN.NET
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.
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] public void modify(SegmentTreeNode root, int index, int value) {
// write your code here
if (root == null) {
return;
}
if (root.start > index || root.end < index) {
return;
}
if (root.start == index && root.end == index) {
root.max = value;
return;
}
int min = root.start + (root.end-root.start)/2;
if (index <= min) {
modify(root.left, index, value);
} else {
modify(root.right, index, value);
}
root.max = Math.max(root.left == null ? Integer.MIN_VALUE : root.left.max,
root.right == null ? Integer.MIN_VALUE : root.right.max);
return;
}
https://codesolutiony.wordpress.com/2015/05/12/lintcode-segment-tree-modify/ public void modify(SegmentTreeNode root, int index, int value) { if (root == null || index > root.end || index < root.start) { return; } if (root.start == root.end) { root.max = value; return; } if (index <= (root.end + root.start) / 2) { modify(root.left, index, value); } else { modify(root.right, index, value); } root.max = Math.max(root.left.max, root.right.max); }
a segment tree is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point. It is, in principle, a static structure; that is, its structure cannot be modified once it is built. A similar data structure is the interval tree.
A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in O(log n + k), k being the number of retrieved intervals or segments
http://techinpad.blogspot.com/2015/05/leetcode-segment-tree-modify.html- void modify(SegmentTreeNode *root, int index, int value) {
- // write your code here
- if(!root) return;
- if(root->start == root->end && root->start == index)
- {
- root->max = value;
- return;
- }
- if(root->start > index || root->end < index) return;
- if(index <= root->left->end) modify(root->left, index, value);
- else modify(root->right, index, value);
- root->max = max(root->left->max, root->right->max);
- }
