一、认识线段树
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);// 更新线段树，更新值为5tree.printTree(root, "");// 打印树}
