2020-04-25 22:57:32
线段树是一棵二叉树，他的每个节点包含了两个额外的属性start和end用于表示该节点所代表的区间。start和end都是整数，并按照如下的方式赋值:
start 和 end 由 build 方法所给出。start=A.left, end=(A.left + A.right) / 2。start=(A.left + A.right) / 2 + 1, end=A.right。start 等于 end, 那么该节点是叶子节点，不再有左右儿子。对于给定数组实现build方法, 线段树的每个节点储存区间最大值, 返回根节点。
/**
* Definition of SegmentTreeNode:
* public class SegmentTreeNode {
* public int start, end, count;
* public SegmentTreeNode left, right;
* public SegmentTreeNode(int start, int end, int count) {
* this.start = start;
* this.end = end;
* this.count = count;
* this.left = this.right = null;
* }
* }
*/
public SegmentTreeNode build(int[] A) {
return helper(A, 0, A.length - 1);
}
private SegmentTreeNode helper(int[] nums, int l, int r) {
if (l > r) return null;
if (l == r) return new SegmentTreeNode(l, r, nums[l]);
int mid = l + (r - l) / 2;
SegmentTreeNode left = helper(nums, l, mid);
SegmentTreeNode right = helper(nums, mid + 1, r);
SegmentTreeNode root = new SegmentTreeNode(l, r, Math.max(left.max, right.max));
root.left = left;
root.right = right;
return root;
}
203. 线段树的修改
对于一棵 最大线段树, 每个节点包含一个额外的 max 属性，用于存储该节点所代表区间的最大值。
设计一个 modify 的方法，接受三个参数 root、 index 和 value。该方法将 root 为根的线段树中 [start, end] = [index, index] 的节点修改为了新的 value ，并确保在修改后，线段树的每个节点的 max 属性仍然具有正确的值。
public void modify(SegmentTreeNode root, int index, int value) {
if (root.start == root.end) {
root.max = value;
return;
}
int mid = root.start + (root.end - root.start) / 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);
}
202. 线段树的查询
对于一个有n个数的整数数组，在对应的线段树中, 根节点所代表的区间为0-n-1, 每个节点有一个额外的属性max，值为该节点所代表的数组区间start到end内的最大值。
为SegmentTree设计一个 query 的方法，接受3个参数root, start和end，线段树root所代表的数组中子区间[start, end]内的最大值。
public int query(SegmentTreeNode root, int start, int end) {
if (root.start == start && root.end == end) return root.max;
int mid = root.start + (root.end - root.start) / 2;
if (start > mid) return query(root.right, start, end);
else if (end <= mid) return query(root.left, start, end);
else return Math.max(query(root.left, start, mid), query(root.right, mid + 1, end));
}
原文：https://www.cnblogs.com/hyserendipity/p/12776071.html