线段树

力扣307

Posted by songjiu on July 14, 2019

线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。线段树方便与求区间段的值(如本题,正常的时间复杂度是N,而使用线段树可以达到LOG(N))、方便更新值以及求最小公倍数公约数(不知道咋弄,以后补充)。

线段树的生成

本题目当中,一个节点的值是他两个子节点的值的和。正常的线段树,应该包含:节点的值、区间段、左右孩子共四个部分。这里使用一个一元线性存储list来存储。由图所示,无论叶子节点(也就是初始值)的数目有多少,使用2*len-1就可以完全存储。
通过倒叙初始数组,将每两个值的和添入list的头部(栈顶),可以构成一个用一元数组表示的线段树,且某节点n的左右孩子分别为:2n+1与2n+2。

线段树值的更新

当一个叶子节点发生改变的时候,相对应的从根节点到该叶子节点的全部节点都会发生变化,因此需要从该叶子节点遍历回根节点,首先根据奇偶性判断该节点为左右哪一节点,然后使用-1 或者-2 再//2向上遍历。

线段树的求和

线段树方便求和,时间复杂度是log(n),因为每个节点存储的值是他的子节点的和,因此假设需要求i到j节点的和,只需要从i和j开始向根节点遍历,二者相遇节点的值就是i到j之和,但是这种情况只存在于i为左节点,j为右节点的正好情况,如果i为右节点,则需要在最后的结果加上i的值,之后i右移一位(正好可以由一个右节点变成一个左节点),j同理。

题目概述

题目概述

代码

    def __init__(self, nums: List[int]):
        #构建线段树,2n+1为左子树,2n+2为右子树
        self.l = len(nums)
        self.nums = [0] * (self.l-1)
        for i in nums:
            self.nums.append( i )
        for i in range(len(nums)-2,-1,-1):
            self.nums[i]=self.nums[2*i+1]+self.nums[2*i+2]
    def update(self, i: int, val: int) -> None:
        i+=self.l-1
        a=val-self.nums[i]
        while i>=0:
            self.nums[i]+=a
            if i%2==1:#判断左右节点
                i=(i-1)//2
            else:
                i=(i-2)//2#找他的父节点
    def sumRange(self, i: int, j: int) -> int:
        sum = 0
        i += self.l-1
        j += self.l-1
        while (i <= j):
            if i%2==0:
                sum+=self.nums[i]
                i+=1
            if j%2==1:
                sum+=self.nums[j]
                j-=1
            i=(i-1)//2
            j=(j-2)//2
        return sum