乐趣区

关于算法:区间算法题用线段树可以秒解

jiezi

区间算法题用线段树能够秒解？

背景

给一个两个数组，其中一个数组是 A [1,2,3,4]，另外一个数组是 B [5,6,7,8]。让你求两个数组合并后的大数组的：

  • 最大值
  • 最小值
  • 总和

这题是不是很简略？咱们间接能够很轻松地在 $O(m+n)$ 的工夫解决，其中 m 和 n 别离为数组 A 和 B 的大小。

那如果我能够 批改 A 和 B 的某些值，并且我要求 很屡次 最大值，最小值和总和呢？

奢侈的思路是原地批改数组，而后 $O(m+n)$ 的工夫从新计算。显然这并没有利用之前计算好的后果，效率是不高的。那有没有效率更高的做法？

有！线段树就能够解决。

线段树是什么？

线段树实质上就是一棵树。更精确地说，它是一颗二叉树，而且它是一颗均衡二叉树。对于为什么是均衡二叉树，咱们前面会讲，这里大家先有这样一个意识。

尽管是一棵二叉树，然而线段树咱们通常应用数组来模仿树结构，而不是传统的定义 TreeNode。

一方面是因为实现起来容易，另外一方面是因为线段树其实是一颗齐全二叉树，因而应用数组间接模仿会很高效。这里的起因我曾经在之前写的堆专题中的二叉堆实现的时候中讲过了，大家能够在我的公众号《力扣加加》回复 堆获取。

解决什么问题

正如它的名字，线段树和线段（区间）无关。线段树的每一个树节点其实都存储了一个 区间（段）的信息 。而后这些区间的信息如果 满足肯定的性质 就能够用线段树来进步性能。

那：

  1. 到底是什么样的性质？
  2. 如何进步的性能呢？

到底是什么样的性质？

比方后面咱们提到的最大值，最小值以及求和就满足这个 肯定性质。即我能够依据若干个（这里是两个）子集推导出子集的并集的某一指标。

以下面的例子来说，咱们能够将数组 A 和 数组 B 看成两个汇合。那么：汇合 A 的最大值和汇合 B 的最大值已知，咱们能够间接通过 max(Amax, Bmax) 求得汇合 A 与汇合 B 的并集的最大值。其中 Amax 和 Bmax 别离为汇合 A 和汇合 B 的最大值。最小值和总和也是一样的，不再赘述。因而如果统计信息满足这种性质，咱们就能够能够应用线段树。然而要不要应用，还是要看用了线段树后，是否能进步性能。

如何进步的性能呢？

对于进步性能，我先卖一个关子，等前面讲完实现的时候，咱们再聊。

实现

以文章结尾的求和为例。

咱们能够将区间 A 和 区间 B 别离作为一个树的左右节点，并将 A 的区间和与 B 的区间和别离存储到左右子节点中。

接下来，将 A 的区间分为左右两局部，同理 B 也分为左右两局部。一直执行此过程直到无奈持续分。

总结一下就是将区间一直一分为二，并将区间信息别离存储到左右节点。如果是求和，那么区间信息就是区间的和。这个时候的线段树大略是这样的：

蓝色字体示意的区间和。

留神，这棵树的所有叶子节点一共有 n 个（n 为原数组长度），并且每一个都对应到原数组某一个值。

体现到代码上也很容易。间接应用 后续遍历 即可解决。这是因为，咱们须要晓得左右节点的统计信息，能力计算出以后节点的统计信息。

不相熟后序遍历的能够看下我之前的树专题，公众号力扣加加回复树即可获取

和二叉堆的示意形式一样，咱们能够用数组示意树，用 2 * i + 1 和 2 * 1 + 2 来示意左右节点的索引，其中 i 为以后节点对应在 tree 上的索引。

tree 是用来构建线段树的数组，和二叉堆相似。只不过 tree[i] 目前存的是区间信息罢了。

下面我形容建树的时候有显著的递归性，因而咱们能够递归的建树。具体来说，能够定义一个 build(tree_index, l, r) 办法 来建树。其中 l 和 r 就是对应区间的左右端点，这样 l 和 r 就能够惟一确定一个区间。tree_index 其实是用来标记以后的区间信息应该被更新到 tree 数组的哪个地位。

咱们在 tree 上存储区间信息，那么最终就能够用 tree[tree_index] = …. 来更新区间信息啦。

外围代码：

def build(self, tree_index:int, l:int, r:int):
    '''
    递归创立线段树
    tree_index : 线段树节点在数组中地位
    l, r : 该节点示意的区间的左，右边界
    '''
    if l == r:
        self.tree[tree_index] = self.data[l]
        return
    mid = (l+r) // 2 # 区间中点，对应左孩子区间完结，右孩子区间结尾
    left, right = 2 * tree_index + 1, 2 * tree_index + 2 # tree_index 的左右子树索引
    self.build(left, l, mid)
    self.build(right, mid+1, r)
    # 典型的后序遍历
    # 区间和应用加法即可，如果不是区间和要改上面这行代码
    self.tree[tree_index] = self.tree[left] + self.tree[right]

下面代码的数组 self.tree[i] 其实就是用来存相似上图中蓝色字体的区间和。每一个区间都在 tree 上存有它一个地位，存它的区间和。

复杂度剖析

  • 工夫复杂度：由递推关系式 T(n) = 2*T(n/2) + 1，因而工夫复杂度为 $O(n)$

不晓得怎么得出的 $O(n)$? 能够看下我的《算法通关之路》的第一章内容。https://leetcode-solution.cn/…

  • 空间复杂度：tree 的大小和 n 同阶，因而空间复杂度为 $O(n)$

终于把树建好了，然而晓得当初一点都没有高效起来。咱们要做的是高效解决 频繁更新状况下的区间查问。

那基于这种线段树的办法，如果更新和查问区间信息如何做呢？

区间查问

先答复简略的问题 区间查问 原理是什么。

如果查问一个区间的信息。这里也是应用后序遍历就 ok 了。比方我要找一个区间 [l,r] 的区间和。

那么如果以后左节点：

  • 残缺地落在 [l,r] 内。比方 [2,3] 残缺地落在 [1,4] 内。咱们间接将 tree 中左节点对于的区间和取出来备用，无妨极为 lsum。
  • 局部落在 [l,r] 内。比方 [1,3] 局部落在 [2,4]。这个时候咱们持续递归，直到残缺地落在区间内（下面的那种状况），这个时候咱们间接将 tree 中左节点对于的区间和取出来备用
  • 将后面所有取出来备用的值加起来就是答案

右节点的解决也是一样的，不再赘述。

复杂度剖析

  • 工夫复杂度：查问不须要在每个时刻都解决两个叶子节点，实际上解决的次数大抵和树的高度一致。而树是均衡的，因而复杂度为 $O(logn)$

或者由递推关系式 T(n) = T(n/2) + 1，因而工夫复杂度为 $O(logn)$

不晓得怎么得出的 $O(logn)$? 能够看下我的《算法通关之路》的第一章内容。https://leetcode-solution.cn/…

大家能够联合前面的代码了解这个复杂度。

区间批改

那么如果我批改了 A[1] 为 1 呢？

如果不批改 tree，那么显然查问的区间只有蕴含了 A[1] 就肯定是错的，比方查问区间 [1,3] 的和 就会失去谬误的答案。因而咱们要在批改了 A[1] 的时候同时去批改 tree。

问题在于 咱们要批改哪些 tree 的值，批改为多少呢？

首先答复第一个问题，批改哪些 tree 的值呢？

咱们晓得，线段树的叶子节点都是原数组上的值，也是说，线段树的 n 个叶子节点对应的就是原数组。因而咱们首先要 找到咱们批改的地位对应的那个叶子节点，将其值批改掉。

这就完了么？

没有完。实际上，咱们批改的叶子节点的所有父节点以及祖父节点（如果有的话）都须要改。也就是说咱们须要 从这个叶子节点一直冒泡到根节点，并批改沿途的区间信息

这个过程和浏览器的事件模型是相似的

接下来答复最初一个问题，具体批改为多少？

对于求和，咱们须要首先将叶子节点改为批改后的值，另外所有叶子节点到根节点门路上的点的区间和都加上 delta，其中 delta 就是扭转前后的差值。

求最大最小值如何更新？大家本人思考一下。

批改哪些节点，批改为多少的问题都解决了，那么代码实现就容易了。

复杂度剖析

  • 工夫复杂度：批改不须要在每个时刻都解决两个叶子节点，实际上解决的次数大抵和树的高度一致。而树是均衡的，因而复杂度为 $O(logn)$

或者由递推关系式 T(n) = T(n/2) + 1，因而工夫复杂度为 $O(logn)$

不晓得怎么得出的 $O(logn)$? 能够看下我的《算法通关之路》的第一章内容。https://leetcode-solution.cn/…

大家能够联合前面的代码了解这个复杂度。

代码

线段树代码曾经放在刷题插件上了，公众号《力扣加加》回复插件即可获取。


class SegmentTree:
    def __init__(self, data:List[int]):
        '''data: 传入的数组'''
        self.data = data
        self.n = len(data)
        #  申请 4 倍 data 长度的空间来存线段树节点
        self.tree = [None] * (4 * self.n) # 索引 i 的左孩子索引为 2i+1，右孩子为 2i+2
        if self.n:
            self.build(0, 0, self.n-1)
    # 实质就是一个自底向上的更新过程
    # 因而能够应用后序遍历，即在函数返回的时候更新父节点。def update(self, tree_index, l, r, index):
        '''
        tree_index: 某个根节点索引
        l, r : 此根节点代表区间的左右边界
        index : 更新的值的索引
        '''
        if l == r==index :
            self.tree[tree_index] = self.data[index]
            return
        mid = (l+r)//2
        left, right = 2 * tree_index + 1, 2 * tree_index + 2
        if index > mid:
            # 要更新的区间在右子树
            self.update(right, mid+1, r, index)
        else:
            # 要更新的区间在左子树 index<=mid
            self.update(left, l, mid, index)
        # 查问区间一部分在左子树一部分在右子树
        # 区间和应用加法即可，如果不是区间和要改上面这行代码
        self.tree[tree_index] = self.tree[left] + self.tree[right]

    def updateSum(self,index:int,value:int):
        self.data[index] = value
        self.update(0, 0, self.n-1, index)
    def query(self, tree_index:int, l:int, r:int, ql:int, qr:int) -> int:
        '''
        递归查问区间 [ql,..,qr] 的值
        tree_index : 某个根节点的索引
        l, r : 该节点示意的区间的左右边界
        ql, qr: 待查问区间的左右边界
        '''
        if l == ql and r == qr:
            return self.tree[tree_index]

        # 区间中点，对应左孩子区间完结，右孩子区间结尾
        mid = (l+r) // 2
        left, right = tree_index * 2 + 1, tree_index * 2 + 2
        if qr <= mid:
            # 查问区间全在左子树
            return self.query(left, l, mid, ql, qr)
        elif ql > mid:
            # 查问区间全在右子树
            return self.query(right, mid+1, r, ql, qr)

        # 查问区间一部分在左子树一部分在右子树
        # 区间和应用加法即可，如果不是区间和要改上面这行代码
        return self.query(left, l, mid, ql, mid) + self.query(right, mid+1, r, mid+1, qr)

    def querySum(self, ql:int, qr:int) -> int:
        '''返回区间 [ql,..,qr] 的和'''
        return self.query(0, 0, self.n-1, ql, qr)

    def build(self, tree_index:int, l:int, r:int):
        '''
        递归创立线段树
        tree_index : 线段树节点在数组中地位
        l, r : 该节点示意的区间的左，右边界
        '''
        if l == r:
            self.tree[tree_index] = self.data[l]
            return
        mid = (l+r) // 2 # 区间中点，对应左孩子区间完结，右孩子区间结尾
        left, right = 2 * tree_index + 1, 2 * tree_index + 2 # tree_index 的左右子树索引
        self.build(left, l, mid)
        self.build(right, mid+1, r)
        # 区间和应用加法即可，如果不是区间和要改上面这行代码
        self.tree[tree_index] = self.tree[left] + self.tree[right]

相干专题

  • 堆

大家能够看下我之前写的堆的专题的二叉堆实现。而后比照学习，顺便还学了堆，岂不美哉？

  • 树状数组

树状数组和线段树相似，难度比线段树略微高一点点。有机会给大家写一篇树状数组的文章。

  • immutablejs

前端的小伙伴应该晓得 immutable 吧？而 immutablejs 就是十分有名的实现 immutable 的工具库。西法之前写过一篇 immutable 原理解析文章，感兴趣的能够看下 https://lucifer.ren/blog/2020…

答复后面的问题

为啥是均衡二叉树？

后面的工夫复杂度其实也是基于树是均衡二叉树这一前提。那么线段树肯定是均衡二叉树么？是的。这是因为线段树是齐全二叉树，而齐全二叉树是均衡的。

当然还有另外一个前提，那就是树的总的节点数和原数组长度同阶，也就是 n 的量级。对于为啥是同阶的，也容易计算，只须要依据递归公式即可得出。

为啥线段树能进步性能？

只有你了解了我 实现局部 的工夫复杂度，那么就不难明确这个问题。因为批改和查问的工夫复杂度都是 $logn$，而不应用线段树的暴力做法查问的复杂度高达 $O(n)$。相应的代价就是建树的 $O(n)$ 的空间，因而线段树也是一种典型的空间换工夫算法。

最初点一下题。区间算法题是否能够用线段树秒解？这其实文章中曾经答复过了，其取决于是否满足两点：

  1. 是否能够依据若干个（这里是两个）子集推导出子集的并集的某一指标。
  2. 是否能进步性能（相比于奢侈的暴力解法）。通常面临 频繁批改 的场景都能够思考应用线段树 优化批改后的查问工夫耗费。
退出移动版