线段树数据结构

Posted by Jason on Monday, April 20, 2020

TOC

介绍线段树前,先了解一下树状数组。他们两个功能差不多,不过有些线段树能够解决的问题,树状数组未必能解决。

树状数组(binary indexed tree)

首先思考一个场景,当有个需求让你求数组中某个区间(0-n、n-m)的和,通常做法是遍历数组求和的方式。这个复杂度为 O(N),但是当区间长度趋向于无穷大时,遍历的开销就不能够忽视了。可以通过树状数组来优化,将区间求和复杂度降低到 O(logN)。

先看一个简单树状结构:

                1-8
               /    \
            1-4      5-8
           /   \    /   \
         1-2  3-4  5-6  7-8
         / \  / \  / \  / \
        1  2  3 4  5 6  7 8

我们可以使用如上的完全二叉树来优化,节点中存储子树的区间和,这样每次求和时可以使用数节点来优化。例如:Sum(3,7)=Sum(3-4)+Sum(5-6)+Sum(7)。但是这样结构带来几个问题:

  1. 存储空间增加一倍(2*n),每个树节点都需要一个空间记录子空间和;
  2. 代码实现复杂度高;
  3. 其中有些节点重复,例如 Sum(3-4) 可以根据 Sum(1-4) 和 Sum(1-2) 计算出来,不需要重复存储;

那么,我们可以将上面结构进行变形,减少存储空间:

                            1-8
                      /     |
                1-4         5-8
           /    |      /    |
        1-2    3-4    5-6   7-8
      /  |    / |    / |   / |
      1  2   3  4   5  6  7  8

变形后会发现,每一列的最顶端的节点是叶子节点的累加和,即:

Sum(1-8) = Sum(1) + Sum(2) + …. + Sum(8) Sum(7) = Sum(7) Sum(1-4) = Sum(1) + Sum(2) + Sum(3) + Sum(4) Sum(5-6) = Sum(5) + Sum(6)

所以只需要 O(N) 的存储空间就能够表示数组的个区间和:

Bit[8] = Sum(8)
Bit[7] = Sum(7)
Bit[6] = Sum(6)
... ...

那下面问题是,如何编码实现呢?有人给出了一个算法 lowbit = n&(-n),它主要求一个数字的二进制表示,右边第一位为1的数字,例如 6 二进制为 0110,lowbit(6) = 2。类似于 cidr 网段的划分 0110 包含的段为 0110 和 0111,其实就是 (0110 -lowbit(0110)+1, 0110) 的区间。

那么 Sum(n) 表达公式为: Sum(n) = Sum(n) + … + Sum(n-lowbit+1)。

那么就伪代码可以编写为:

func update(idx, diff):
    for idx <= n:
        Sum(idx) += diff
        idx += lowbit(idx) 

func getSum(idx):
    for idx > 0:
        sum += Sum(idx)
        idx -= lowbit(idx)

「真诚赞赏,手留余香」

Jason Blog

真诚赞赏,手留余香

使用微信扫描二维码完成支付


comments powered by Disqus