线段树的实现(思路分析)

线段树的实现(思路分析)

这里我们实现的是普通的线段树, 而不是zkw线段树

线段树实现时可以是基于两种数据结构的:

1. array based —> 基于数组实现
2. tree based —> 基于树
   • 这里我们是基于树实现的

接下来我们来讲如何基于树实现线段树:

第一: 首先

来讲解如何定义结点类

1. 定义左右指针域(只要是二叉树都是有左右子指针域的)
2. 定义两个整形变量start和end表示当前节点表示的区间范围
   • 因为线段树中每个结点都表示了一个区间范围, 即使是叶子结点也是表示一个区间, 只不过区间的长度为1
3. 定义一个整形变量sum表示当前节点对应区间上的所有结点的和
4. 提供一个有参构造, 其中有两个形参就可了, int start 和 int end , 因为我们在构建线段树的时候要使用到这样的有参构造

第二: 创建线段树类:

1. 定义一个int[] (成员变量)和一个root(根节点)

   • 因为此时我们构建线段树的时候是要传入一个序列, 也就是传入一个数组, 然后我们要基于这个数组来构建线段树, 每个线段树中的int[]的初始化我们要通过对外的有参构造来完成, 我们传入一个int[]之后, 我们要根据这个有参构造来完成线段树的创建, 这个int[]中存放的其实就是每个叶子结点的值
   • 我们这类之所以要声明这个int[]其实也就是因为我们这个时候int[]是通过线段树类的有参构造传入的, 但是具体使用的时候却要是在构建线段树的方法中使用, 所以为了整个类中不同的方法中可以使用到这个int[], 这个时候我们只能通过声明一个成员位置的int[]来完成

2. 提供有参构造

   • 我们在有参构造中给成员变量nums(int[]) 赋值, 之后调用线段树类中的构建线段树的方法即可, 调用的时候将nums传入到构建线段树的方法中即可, 最终我们的构建线段树的方法中会返回构建的线段树的根节点, 我们将这个返回值赋值给root即可

3. 提供创建线段树的方法(递归方法)

   • 入参: int [] , int start, int end
     • int[] 就是要构建线段树的序列, start和end表示区间, 第一次的时候肯定是从0到nums.length- 1的区间的全部元素
     • 这里我们的入参中要显示的给定start和end是因为我们此时构建线段树的方法是一个递归方法, start和end的值是会变化的, 所以一定要将start和end写到形参位置
   • 返回值: Node类型, 最终会返回创建的线段树的头结点
   • 具体实现操作:
     1. 我们先判断如果start大于end, 则直接返回一个null(因为start > end时这个区间的范围就是不合理的,所以我们就返回一个null)
     2. 如果start <= end, 这个时候又分为了两种情况, 一种是start = end, 一种是start < end, 但是不管是这两种情况的任何一种, 我们此时表示当前区间是存在的, 那么我们就要对应区间范围创建一个节点, 创建的这个节点表示的区间范围就是start 到 end之间, 也就是new Node(start, end) —> 所以这个也就是为什么我们要在Node节点类中提供有两个形参int start 和int end的有参构造了
        1. 如果start = end , 那么表示此事的Node就是叶子结点了, 我们直接将此结点的num(区间和)值修改为数组中对应索引为start位置的值即可, 因为数组中其实存储的就是叶子结点的值
        2. 如果是start < end , 那么这个时候表示此时我们要创建一个表示区间的Node节点, 此时我们创建完成这个节点之后就要继续向下去创建, 也就是创建这个节点的子节点, 所以这里我们要引入一个mid, 为我们首先此时要计算出mid的值, 就是求出这个区间的中间索引(mid = start + (end - start)/2), 然后我们就递归的去创建这个节点的左子节点和右子节点, 我们的左子节点的区间范围就是此时当前节点(也就是父节点)的start 到 mid之间包括start和mid , 我们的右子节点的区间范围就是当前节点的mid + 1到 end之间包括mid + 1和end,然后我们一直递归向下处理即可

4. 编写单点修改的方法(递归方法):

   • 入参: Node node, int i, int val
     • node就是当前遍历到的结点, 也就是我们在判断的结点, 最开始的时候我们的node结点肯定是从根节点开始的, 因为我们要找修改第i个值, 那么我们肯定是要先找到第i个叶子结点, 那么我们肯定是从根节点开始遍历查找
     • i就是我们要修改的结点的索引, 也就时我们要修改的结点是数组中的第几个结点
     • val就是我们要将结点修改为的目标值
   • 返回值: void , 这个时候我们只是对这个元素进行一个修改, 我们并不需要有返回值
   • 具体实现操作:
     1. 我们判断如果node.start = node.end, 那么就表示找到了我们要修改的结点, 那么我们直接将这个节点的值修改就可以了
     2. 但是这个时候我们将这个叶子结点修改之后, 对应的父节点的值也要发生改变, 因为这个时候叶子结点的值都变化了, 父节点是区间之内的叶子结点的值的求和, 这个时候父节点的值肯定也是要发生改变的, 这个时候父节点的值的改变我们最终会在回溯的时候完成
     3. 如果node.start != node.end, 那么这个时候就表明这个节点是一个非叶子结点, 也就是这个节点表示的是一个区间, 这个时候我们就要判断i和mid的值的大小, 如果i <= mid, 那么我们就要去当前节点的左子树上去查找要修改的结点, 如果i > mid, 那么我们就要去当前节点的右子树上去查找我们要修改的结点

• 其实对于这个方法, 我们可以对外提供一个外界使用的单点修改的方法, 然后再编写一个专门的私有的用来递归的方法, 来完成递归执行操作

5. 编写区间求和的方法(递归方法):
   • 入参: Node node, int start, int end
     • node第一次的时候就传入root, 因为我们要从根节点开始判断, 一直向下递归, 直到计算出我们的目标区间的值的和为止
     • start和end就确定了我们求和的区间
   • 返回值: int
     • 将求和的结果返回
   • 具体实现操作:
     1. 也是先判断start是否大于end ,如果start >end, 那么我们直接就返回一个0即可, 因为start > end的区间根本就是不存在的
     2. 如果当前形参中的start和end等于当前node的node.start和node.end ,则就说明找到了这个区间对应的结点, 我们直接将node.num返回即可, 这个时候注意, 我们返回的这个node.num的值用于在上一层递归中来求和, 因为随着不断的递归, 我们最终是将原本的区间拆分开之后去计算的值, 最终计算出结果之后统统将结果又进行一个相加求和
     3. 如果形参中的start和end不等于当前node的node.start和node.end,那么我们就计算出根据node.start和node.end计算出mid的值, 然后使用这个mid值做一个判断
        1. 如果形参中的start > mid, 那么我们就去当前节点的右子树上找
        2. 如果形参中的end < mid, 那么我们就去当前节点的左子树上找
        3. 如果mid 在 start和end之间, 那么我们去左树上找start 到 mid区间的结点和, 去右树上找mid + 1到 end区间的结点和
     4. 我们这个时候也是在回溯的时候才将计算出的每个分区间的和加到一起, 只有我们的待求区间分布在结点的mid两边的时候, 这个时候我们就需要将区间分割之后进行计算, 只要区间分割之后计算之后那么我们回溯的时候肯定就要对分割的值进行一个求和