常用数据结构之前缀树_线段树_树状数组

迷南。 2022-12-15 06:06 222阅读 0赞

## 1.前缀树 ##

如下图所示，将单词拆分为字符，用从根节点到终点(黑色部分)所有路径上的字符来表示一个单词。如012用来表示in,0124用来表示int。这样将单词公共部分统一提取出来，节约存储空间，方便进行联想查找。常用在搜索引擎、输入法中的联想功能。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center]

## 2.前缀树python实现 ##

代码参考[前缀树的python实现][python]

#File Name : 前缀树.py
    class TrieNode(object):
        def __init__(self):
            # 路过此节点的节点数,即以该路径为前缀的路径
            self.path = 0
            #以此为结尾的几个,即以该路径为后缀的路径
            self.end = 0
            # 每一个节点有26条路
            #列表生成式 初始化列表中有26个None
            self.map = [None for i in range(26)]
    class Trie(object):
        def __init__(self):
            self.root = TrieNode()
        def insert(self,word):
            if word == None:
                return
            node = self.root
            for i in word:
                #单词的下标 从a开始当作0
                index = ord(i) - ord('a')
                #ord 为ASCII吗
                if node.map[index] == None:
                    node.map[index] = TrieNode()
                node = node.map[index]
                node.path += 1
            node.end+=1
            print('insert successful ！！！')
        def search(self,word):
            if word == None:
                return 0
            node = self.root
            for i in word:
                index = ord(i)-ord('a')
                if node.map[index]==None:
                    return 0
                node = node.map[index]
            return node.end
        def delete(self,word):
            if self.search(word) != 0:
                node = self.root
                for i in word:
                    index = ord(i)-ord('a')
                    node.map[index].path -=1
                    if node.map[index].path==0:
                        #本来原来就有一个  再删一个 就没了
                        #变成0 代表不需要此节点了
                        node.map[index] = None
                        return
                    node = node.map[index]
                node.end-=1
        def prefixNumber(self,pre):
            if pre == None:
                return
            node = self.root
            for i in pre:
                index = ord(i)-ord('a') 
                if node.map[index] == None:
                    return 0
                node = node.map[index]
            return node.path

## 3.线段树 ##

线段树是一棵完全二叉树，考虑这样一种需求，我们需要经常查询一个数组中区间的和，并且经常更新，或者算出区间的最大值。普通数组查询的复杂度为O(n),更新的复杂度为O(1)。查询严重影响到了速度。对其进行优化，提出了线段树的概念。  
线段树是一棵完全二叉树，每个节点存储一个区间的和。根节点区间为所有元素，使用二分的思想将根区间分为两份(若不能平均分时左子节点用大的区间)，分为左子节点和右子节点的区间。迭代的生成整棵树，单个元素作为树的叶子节点。  
线段树最常用的操作是区间查询和单点更新：  
**1.区间查询：**  
1.如果当前区间是目标区间的子集，则返回  
2.如果当前区间左子节点和目标区间有交集，遍历左子节点，直到满足条件1  
3.如果当前区间右子节点和目标区间有交集，遍历右子节点，直到满足条件1  
4.将所有返回的区间值相加  
如下图所示(注意图中框内元素表示的是区间，如根节点表示区间\[1 10\])，如果要查询区间\[2 5\]的值，根节点区间没有完全包括在内，左子节点有交集，于是遍历左子节点。按照上面的方法继续遍历，最终我们返回点的区间为\[2\]、\[3\]、\[4 5\]，再将三个区间的值相加。  
区间内的最大值思路也一样，最后将返回区间的值比较求最大即可。  
**2.单点更新**  
找到要访问的叶子节点，沿着访问路径更新所有节点的值(根节点的值等于左右子节点之和)。时间复杂度为log(n)，解释一下这里复杂度的计算：对于完全二叉树来说，第n个节点位于log(n)层，更新的时候每一层都会有一个节点被更新，所以时间复杂度为log(n)  
**3.区间更新**  
当一个区间的元素需要被更新时，我们只更新到目标区间的真子集就停止更新。然后在该子集添加lazy\_tag，下一次用到(查询或修改)该子集时再更新子集的左右节点，并将lazy\_tag传给子集。  
**4.存储空间4n说明**  
如果元素个数K正好是2n,我们使用K+K-1的空间即可存储；如果元素K是2n\+1时，我们需要单独开出一层只有一个节点，这是倒数第二层为K-1个节点，倒数第二层上面为K-2个节点。最后一层虽然只有一个节点有用，但空出来的节点需要填满，需要的空间为2(K-1)。这是最坏的情况，总共需要的空间为(K-1)+(K-2)+2(K-1)=4K-5。所以，使用数组存储时，为了保证空间够用，我们一般开4n(n是元素个数)的空间。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 1]

## 4.线段树python实现 ##

使用迭代的方式实现线段树的单点更新和区间查询功能，源码参考[线段树的python实现一文][python 1]

#-*- coding:utf-8 -*-
    #单点更新  区间查询
    # 线段树的节点类
    class TreeNode(object):
        def __init__(self):
            self.left = -1 #左区间
            self.right = -1 #右区间
            self.sum_num = 0 #区间和
    # 线段树类
    # 以_开头的是递归实现
    class Tree(object):
        def __init__(self, n, arr):
            self.n = n #节点数
            self.max_size = 4 * n #总空间大小
            self.tree = [TreeNode() for i in range(self.max_size)]  # 维护一个TreeNode列表
            self.arr = arr #列表的值
        # index从1开始 数组下标
        #迭代生成线段树
        def _build(self, index, left, right):
            self.tree[index].left = left
            self.tree[index].right = right
            if left == right:
                self.tree[index].sum_num = self.arr[left - 1]
            else:
                mid = (left + right) // 2
                #index * 2 为左子节点 index * 2 + 1 为右子节点
                self._build(index * 2, left, mid)
                self._build(index * 2 + 1, mid + 1, right)
                #计算节点的和
                self.pushup_sum(index)
        # 构建线段树
        def build(self):
            self._build(1, 1, self.n)
        #点更新 沿着路径更新所有的点
        def _update(self, point, val, i, l, r, ):
            if self.tree[i].left == self.tree[i].right:
                self.tree[i].sum_num += val
            else:
                mid = (l + r) // 2
                if point <= mid:
                    self._update(point, val, i * 2, l, mid)
                else:
                    self._update(point, val, i * 2 + 1, mid + 1, r)
                    # 根据左右子树更新当前的值
                self.pushup_sum(i)
        # 单点更新
        # point 要更新的数在数组的下标 val更新的值
        def update(self, point, val, ):
            self._update(point, val, 1, 1, self.n)
        # 求和
        def pushup_sum(self, k):
            self.tree[k].sum_num = self.tree[k * 2].sum_num + self.tree[k * 2 + 1].sum_num
        #区间查询
        def _query(self, ql, qr, i, l, r, ):
            if l >= ql and r <= qr:  # 如果当前区间是目标区间的真子集，则返回
                return self.tree[i].sum_num
            else:
                mid = (l + r) // 2
                res_l = 0
                res_r = 0
                if ql <= mid:  # 左子树最大的值大于了查询范围最小的值-->左子树和需要查询的区间交集非空
                    res_l = self._query(ql, qr, i * 2, l, mid, )
                if qr > mid:  # 右子树最小的值小于了查询范围最大的值-->右子树和需要查询的区间交集非空
                    res_r = self._query(ql, qr, i * 2 + 1, mid + 1, r, )
                return res_l + res_r
        # 区间查询
        def query(self, ql, qr):
            return self._query(ql, qr, 1, 1, self.n)
        # 深度遍历打印数组
        def _show_arr(self, i):
            if self.tree[i].left == self.tree[i].right and self.tree[i].left != -1:
                print(self.tree[i].sum_num, end=" ")
            if 2 * i < len(self.tree):
                self._show_arr(i * 2)
                self._show_arr(i * 2 + 1)
        # 显示更新后的数组的样子
        def show_arr(self, ):
            self._show_arr(1)
    def test():
        n = 5
        arr = [1, 5, 4, 2, 3]
        tree = Tree(n, arr) #初始化树
        tree.build()#构造树
        tree.update(1, 3)#单点更新
        res = tree.query(2, 5) #区间查询
        print(res)
    if __name__ == '__main__':
        test()
        # line1 = [int(x) for x in input().strip().split(" ")]
        # n = line1[0]  # 数字的个数
        # m = line1[1]  # 操作的个数
        # arr = [int(x) for x in input().strip().split(" ")]
        # tree = Tree(n, arr)
        # tree.build()
        # for i in range(m):
        #     line = [int(x) for x in input().split(" ")]
        #     op = line[0]
        #     if op == 1:
        #         tree.update(line[1], line[2])
        #     elif op == 2:
        #         res = tree.query(line[1], line[2])
        #         print(res)

**区间更新**  
使用Lazy\_tag。每次只更新到当前区间的真子集，等下一次用到其真子集的时候再去更新左右子节点的值和Lazy\_tag

#-*- coding:utf-8 -*-
    #区间更新 区间查询
    # 线段树的节点类
    class TreeNode(object):
        def __init__(self):
            self.left = -1
            self.right = -1
            self.sum_num = 0
            self.lazy_tag = 0
        # 打印函数
        def __str__(self):
            return '[%s,%s,%s,%s]' % (self.left, self.right, self.sum_num, self.lazy_tag)
        # 打印函数
        def __repr__(self):
            return '[%s,%s,%s,%s]' % (self.left, self.right, self.sum_num, self.lazy_tag)
    # 线段树类
    # 以_开头的是递归实现
    class Tree(object):
        def __init__(self, n, arr):
            self.n = n
            self.max_size = 4 * n
            self.tree = [TreeNode() for i in range(self.max_size)]  # 维护一个TreeNode数组
            self.arr = arr
        # index从1开始
        def _build(self, index, left, right):
            self.tree[index].left = left
            self.tree[index].right = right
            if left == right:
                self.tree[index].sum_num = self.arr[left - 1]
            else:
                mid = (left + right) // 2
                self._build(index * 2, left, mid)
                self._build(index * 2 + 1, mid + 1, right)
                self.pushup_sum(index)
        # 构建线段树
        def build(self):
            self._build(1, 1, self.n)
        #只更新真子集的值  下次用到真子集时再更新其左右节点
        def _update2(self, ql, qr, val, i, l, r, ):
            mid = (l + r) // 2
            # 如果是目标区间的真子集则更新  lazy_tag 为 val的值
            if l >= ql and r <= qr:
                self.tree[i].sum_num += (r - l + 1) * val  # 更新和
                self.tree[i].lazy_tag += val  # 更新懒惰标记
            else:
                self.pushdown_sum(i)
                if mid >= ql:
                    self._update2(ql, qr, val, i * 2, l, mid)
                if qr > mid:
                    self._update2(ql, qr, val, i * 2 + 1, mid + 1, r)
                self.pushup_sum(i)
        # 区间修改
        def update2(self, ql, qr, val, ):
            self._update2(ql, qr, val, 1, 1, self.n)
        def _query2(self, ql, qr, i, l, r, ):
            if l >= ql and r <= qr:  # 若当前范围包含于要查询的范围
                return self.tree[i].sum_num
            else:
                self.pushdown_sum(i)  # modify
                mid = (l + r) // 2
                res_l = 0
                res_r = 0
                if ql <= mid:  # 左子树最大的值大于了查询范围最小的值-->左子树和需要查询的区间交集非空
                    res_l = self._query2(ql, qr, i * 2, l, mid, )
                if qr > mid:  # 右子树最小的值小于了查询范围最大的值-->右子树和需要查询的区间交集非空
                    res_r = self._query2(ql, qr, i * 2 + 1, mid + 1, r, )
                return res_l + res_r
        def query2(self, ql, qr):
            return self._query2(ql, qr, 1, 1, self.n)
        # 求和,向上更新
        def pushup_sum(self, k):
            self.tree[k].sum_num = self.tree[k * 2].sum_num + self.tree[k * 2 + 1].sum_num
    
        # 向下更新lazy_tag
        def pushdown_sum(self, i):
            lazy_tag = self.tree[i].lazy_tag
            #更新当前节点的左子节点和右子节点的值和lazy_tag
            if lazy_tag != 0:  # 如果有lazy_tag
                self.tree[i * 2].lazy_tag += lazy_tag  # 左子树加上lazy_tag
                self.tree[i * 2].sum_num += (self.tree[i * 2].right - self.tree[i * 2].left + 1) * lazy_tag  # 左子树更新和
                self.tree[i * 2 + 1].lazy_tag += lazy_tag  # 右子树加上lazy_tag
                self.tree[i * 2 + 1].sum_num += (self.tree[i * 2 + 1].right - self.tree[
                    i * 2 + 1].left + 1) * lazy_tag  # 右子树更新和
                self.tree[i].lazy_tag = 0  # 将lazy_tag 归0
        # 深度遍历
        def _show_arr(self, i):
            if self.tree[i].left == self.tree[i].right and self.tree[i].left != -1:
                print(self.tree[i].sum_num, end=" ")
            if 2 * i < len(self.tree):
                self._show_arr(i * 2)
                self._show_arr(i * 2 + 1)
        # 显示更新后的数组的样子
        def show_arr(self, ):
            self._show_arr(1)
        def __str__(self):
            return str(self.tree)
    # 落谷测试用例1
    def test():
        n = 5  # 1 5 4 2 3
        arr = [1, 5, 4, 2, 3]
        tree = Tree(n, arr)
        tree.build()
        tree.update2(2, 4, 2)
        res = tree.query2(3, 3)
        print(res)
    if __name__ == '__main__':
        test()
        # line1 = [int(x) for x in input().strip().split(" ")]
        # n = line1[0]  # 数字的个数
        # m = line1[1]  # 操作的个数
        # arr = [int(x) for x in input().strip().split(" ")]
        # tree = Tree(n, arr)
        # tree.build()
        # for i in range(m):
        #     line = [int(x) for x in input().split(" ")]
        #     op = line[0]
        #     if op == 1:
        #         tree.update2(line[1], line[2], line[3])
        #     elif op == 2:
        #         res = tree.query2(line[1], line[1])
        #         print(res)

## 5.树状数组 ##

树状数组和线段树的思想非常相似，都是将数组一定区间的和存储在另外一个数组中。方便进行区间查询和单点更新，时间复杂度都为O(logn)。  
更线段树中二分法的思想不同，树状数组每个节点存储哪些区间的和是通过Lowbit函数计算出来的。  
lowbit(i)函数返回的是**二进制中i最后一个1所代表的数字**。其计算公式如下：((Not I)+1) And I，程序实现时可以发现((Not I)+1) 正好就是-I的值(因为计算机负值就是这么存储的),所以lowbit(i) = i & (-i)  
用下图来验证(我们用A表示源数组、C表示生成的树状数组)：  
lowbit(1) = 1 包含空间为1 C1 = A1  
lowbit(2) = 2 包含空间为2 C2 = A2+A1  
lowbit(3) = 1 包含空间为1 C3 = A3  
lowbit(4) = 4 包含空间为4 C4 = A4+A3+A2+A1  
lowbit(5) = 1 包含空间为1 C5 = A5  
…  
lowbit(8) = 8 包含空间为8 C4 = A8+A7+A6+A5+A4+A3+A2+A1  
**构建树状数组**  
如上所示，每个位置i包含的区间为由当前位置往下取lowbit(i)个。我们按顺序将每个点插入，更新当前点的值，并且更新所有包含它的点，不断更新i+lowbit(i)位置，直到i+lowbit(i)大于数组长度。  
**点更新**  
上面我们讲的构建数组，其实就是多个更新的过程。当一个点更新的时候，包含该点的位置就是i+lowbit(i)，然后迭代的将包含的位置全部更新。  
**区间和查询**  
查询和更新是相反的操作，先找到当前位置的值，再迭代的找i-lowbit(i)，直到i<=0；比如要查找8之前的区间和，先取8位置的值，再取8-lowbit(8)=0所以不再取。我们看到8处的值已经包含了前面区间的和  
![在这里插入图片描述][20201016220046920.png_pic_center]

## 6.树状数组python实现 ##

#-*- coding:utf-8 -*-
    class FenwickTree:
        def __init__(self, arrayA):  # 传入初始数组，构建树状数组
            self.size = len(arrayA)  # 保存数组大小
            self.arrayA = [0 for i in range(self.size)] #保存初始数组以及变更
            #树状数组初始设置为0
            self.arrayC = [0 for i in range(self.size)]
            for i in range(1,self.size+1):
                """
                构建类的初始数组A和树状数组B
                这里有一个注意事项，我们对于求前缀和与单点更新时，树状数组C是拿来直接使用的，
                那么问题来了，树什么时候建立好的，我怎么不知道？?
                事实上，对于一个输入的数组A，我们一次读取的过程，就可以想成是一个不断更新值的过程
                （把A1~An从0更新成我们输入的A[i]），所以一边读入A[i]，一边将C[i]涉及到的祖先节点值更新，
                 完成输入后树状数组C也就建立成功了
                """
                self.update(i,arrayA[i-1]) #【注意】数组从0下标开始，update方法从1开始
        def lowbit(self,m):
            """
            求出m的二进制表示的末尾1的位置
            :return:
            """
            return m & (-m)
        def update(self, i, val):  # 【注意】数组从0下标开始，update方法从1开始
            self.arrayA[i-1] += val  # 更新初始数组
            while i <= self.size:
                self.arrayC[i-1] += val #注意数组下标从0开始
                i += self.lowbit(i) #返回二进制中最后一个1所代表的值
        def sum(self, i):  # 求前缀和，sum方法从1开始
            ans = 0
            while i > 0:
                ans += self.arrayC[i-1] #数组下标从1开始
                i -= self.lowbit(i)
            return ans
    if __name__ == "__main__":
        fenwickTree = FenwickTree([1,2,3,4,5,6,7,8])
        print(fenwickTree.arrayA) #打印初始数组
        print(fenwickTree.arrayC) #打印树状数组
        print(fenwickTree.sum(4))#求arrayA前4项的和
        fenwickTree.update(1,3) #arrayA第1个元素+3
        print(fenwickTree.arrayA)  # 打印更新数组[4,2,3,4,5,6,7,8]
        print(fenwickTree.arrayC)  # 打印树状数组
        print(fenwickTree.sum(4))#求arrayA前4项的和

## 7.总结 ##

本文我们介绍了常用的三种树结构，前缀树是使用树的路径上所有节点表示单词，这样可以把单词之间公共的部分提取出来，提高了存储效率。方便我们进行联想查询类的操作；接着我们讲述了线段树，树中的每个节点表示一定区间的和，采用二分法的思想，每一个父节点分为两份，第一份是左子节点，第二份是右子节点。方便处理区间求和问题、区间最值问题等。最后我们聊了树状数组，思想和线段树一样，都是用节点存储区间的和。只是节点代表的区间我们用lowbit函数来计算，lowbit(i)表示二进制的i最后一个1所表示的数。树状数组也常用来解决区间和问题，属于简单版的线段树。

## 8. 冰与火之歌 ##

如果我能看的见，阳光从天上泼洒下来，周围的事物都变得五彩斑斓，我就觉得一切都好像飞起来了一样；如果我能听得见，我跟这个世界就不再是隔离的，能够听得见人们的笑声，我自己也会笑；如果我能够站起来，我就要奔跑，一连跑十几个小时直到筋疲力尽。我要跳舞，欢快的舞步跟着每一个节拍；可是，卧槽！我居然真的看得见、听得见、也能站起来。可是我还要上课，还要看电视，我没有时间去干别的。所以！只有夜晚闭上眼睛，想象自己是一个六识尽失的人，我才能够完完全全的体会到生而为人的快乐。

冰与火之歌 主题曲

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/960f3ccbf0c14c108683aac902193551.png
[python]: https://blog.csdn.net/weixin_40274123/article/details/94026945
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2dhb2JpbmcxOTkz_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/db0d0f7e399a40db8207ff475cec6b8c.png
[python 1]: https://blog.csdn.net/qq_33935895/article/details/102806357
[20201016220046920.png_pic_center]: /images/20221123/8411cb2463274bdf8770c0ca0333631e.png