线段树-认识线段树+实现线段树
一、认识线段树
1、定义
线段树是平衡二叉树
2、特点
线段树将一个区间划分成单元区间，每个单元区间对应线段树中的一个结点
3、应用
频繁查找一个数组中指定区间内的和、最值
学了动态规划后使用迭代要好过使用递归，因为递归每次进去是有空间损耗的
二、线段树的实现（放数据、查数据）
1、线段树节点
/*
线段树节点类
*/
public class SegmentNode {
public int start;// 区间起点
public int end;// 区间终点
public int sum;// 区间内求和
public SegmentNode left;
public SegmentNode right;
public SegmentNode(int start, int end) {
this.start = start;
this.end = end;
}
}2、线段树的创建
/*
线段树类
*/
public class SegmentTree {
private int[] elements;// 接收外界传入的数据
public SegmentTree(int[] elements) {
this.elements = elements;
}
public SegmentNode buildTree(int start,int end){
if(start > end){
return null;
}
SegmentNode newNode = new SegmentNode(start,end);
if(start == end){
newNode.sum = elements[start];
return newNode;
}
// 当start < end时，由于线段树是节点区间整体取值，因此要进行递归，求取左右子树的值
int mid = start + (end - start)/2;// 获取区间中点 不使用mid = (start + end)/2的原因是可能会超出int类型的最大值
newNode.left = buildTree(start,mid);
newNode.right = buildTree(mid + 1,end);
newNode.sum = newNode.left.sum + newNode.right.sum;
return newNode;
}
}3、打印线段树中的数据
（1）四种方式
- 前序遍历：中左右
- 中序遍历：左中右
- 后序遍历：左中右
（2）前序遍历打印线段树中的数据
- 核心代码
public void printTree(SegmentNode root,String prefix){
System.out.println(prefix + "Node [" + root.start + "," + root.end + "] sum: " + root.sum);
if(root.left != null){
printTree(root.left, prefix+" ");
}
if(root.right != null){
printTree(root.right, prefix+ " ");
}
}- 测试代码
public static void main(String[] args) {
int[] nums = {1, 11, 5, 7, 9, 2};
SegmentTree tree = new SegmentTree(nums);// 创建树
SegmentNode root = tree.buildTree(0,nums.length-1);// 向树中放入数据
tree.printTree(root, "");// 打印树
}- 结果输出
4、在线段树中查询给定区间的和
（1）核心代码
public int query(SegmentNode root,int start,int end){
// 所给区间与线段树区间无交集
if(start > root.end || end < root.start){
return 0;// 0: 作用1：代表所给区间与线段树无交集 作用2:不会影响给定区间求和
}
// 所给区间包含线段树区间
if(start <= root.start && end >= root.end){
return root.sum;// !!! 这一块要返回的是当前结点的和
}
// 所给区间与线段树区间有部分交集
int leftSum = query(root.left,start,end);
int rightSum = query(root.right,start,end);
return leftSum + rightSum;
}（2）测试代码
public static void main(String[] args) {
int[] nums = {1, 11, 5, 7, 9, 2};
SegmentTree tree = new SegmentTree(nums);// 创建树
SegmentNode root = tree.buildTree(0,nums.length-1);// 向树中放入数据
tree.printTree(root, "");// 打印树
System.out.println(tree.query(root,1,3));// 查询给定区间的和
}（3）结果输出
5、更新线段树中每个节点的sum属性的值（即给原来的每个数组元素的值都加上指定大小的更新新值）
（1）优化代码的思想：要做一件事情的时候，先将这件事情攒着，当到达某一时间点的时候，把攒着的事情一块一做
（2）在线段树中，pushDown()方法用于实现懒更新策略。懒更新策略允许我们在更新操作时避免不必要的子树遍历，只在真正需要时才将更新值下推到子节点，在节点中添lazy属性记录lazy值
（3）如果我们每进行一次加值的操作，就将全部线段树更改一遍，时间复杂度会很高，因此，我们需要进行一个延迟加和的操作
（4）具体思路：如果【left，right】区间增加a，在查询时，就可以把【left，right】区间标记的增加量推下去就可以直接求值了
（5）pushDown()方法
public void pushDown(SegmentNode node){
// 子节点不存在不需要下推
if(node.left == null || node.right == null){
return;
}
if(node.lazy != 0){
node.left.sum += node.lazy * (node.end - node.start + 1);
node.left.lazy += node.lazy;
node.right.sum += node.lazy * (node.end - node.start + 1);
node.right.lazy += node.lazy;
}
node.lazy = 0;
}（6）update方法
缺点：不能将所有节点的sum属性的值全部正确更新
public SegmentNode update(SegmentNode root,int start,int end,int updateVal){
// 给定区间与线段树区间无交集
if(start > root.end || end < root.start){
return null;// 给定区间有误，未进行更新操作
}
// 给定区间包含线段树区间
if(start<=root.start && end>=root.end){
root.sum += (root.end - root.start + 1)*updateVal;
root.lazy += updateVal;
return root;
}
pushDown(root);
update(root.left,start,end,updateVal);
update(root.right,start,end,updateVal);
root.sum = root.left.sum + root.right.sum;
return root;
}（7）测试代码
public static void main(String[] args) {
int[] nums = {1, 3, 5, 7, 9, 11};
SegmentTree tree = new SegmentTree(nums);// 创建树
SegmentNode root = tree.buildTree(0,nums.length-1);// 向树中放入数据
tree.printTree(root, "");// 打印树
System.out.println("---------------------");
tree.update(root,1,4,5);// 更新线段树，更新值为5
tree.printTree(root, "");// 打印树
}
原文地址：https://blog.csdn.net/Watermelon_Mr/article/details/142134857
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！