线段树——入门

客官°小女子只卖身不卖艺 2022-05-22 10:14 124阅读 0赞

此博客参考了[线段树从零开始][Link 1]。考虑读者已阅读参考博客。

*  存储sum用数组的长度
 *  线段树——建树
 *  线段树——单点修改
 *  线段树——查询sum

# 存储sum用数组的长度 #

参考博客提出，用数组来存储各个节点（每个节点存储的是，该节点代表区间内数的总和）的sum，就不需要弄成，建立树节点的class，还为这个class提供左右孩子的方法之类的，直接用数组来代替原二叉树结构。  
但参考博客提出，sum数组的长度为存数数组的长度的4倍，其实不对，只要得到树的层数h，再得到h层的完全二叉树的最大节点数，再加一个1，就是sum数组的长度。

#利用递归，深度遍历到第一个终点，这个叶子节点必定在二叉树的最后一层
    #（通过画二叉树可以发现上述成立）
    #便得到了二叉树的层数
    #因为是二叉树，虽然不是完全二叉树，但用完全二叉树来存储就可以使用
    #性质：节点索引从1开始，i节点的左孩子为2i，右孩子为2i+1
    #所以，只要获得该二叉树的层数，再以完全二叉树的最大节点数作为数组的长度
    def get_ceng(l,r):
        if(l==r):
            return 1;
        m=(l+r)//2
        return get_ceng(l,m)+1
    
    def get_length(l,r):
        ceng = get_ceng(l,r)
        print(ceng)
        length = 2**ceng-1#n层的完全二叉树，节点数最大为2的n次方-1
        length = length+1#因为索引是从1开始用的，0索引没有用，但必须得浪费，所以加1
        return length
    
    print(get_length(0,12))

运行结果：![这里写图片描述][201806220836385]。5代表二叉树层数，32代表存储数组需要的长度。参考博客是传入参数是1,13.本文是0,12，但画出来二叉树结构是一样的，只是每个索引都减一。  
总结：不管画出来的二叉树是啥样，是不是完全二叉树，都可以按照完全二叉树来存储，虽然会浪费掉一些空间，但就可以使用完全二叉树的良好性质：如果节点索引从1开始，那么i节点的左孩子为2i，右孩子为2i+1。  
原文线段树结构：  
![这里写图片描述][20180622083924438]  
本文线段树结构：  
![这里写图片描述][2018062208413153]

# 线段树——建树 #

#有两种索引，一是完全二叉树的节点索引，该索引从1开始，为了方便计算
    #一种是原数组的索引，该索引从0开始，从1开始都可以，本文从0
    num=[1,2,3,4,1,2,3,4,1,2,3,4,1]
    
    length = get_length(1,13)
    sum_list=[0]*length
    
    def pushup(rt):
        sum_list[rt]=sum_list[2*rt]+sum_list[2*rt+1]
    
    def build(l,r,rt):#l为区间左端点，r为区间右端点，rt为完全二叉树索引
        #l,r也是num的索引；第一次调用时，rt为1
        if(l==r):
            sum_list[rt]=num[l]
            return
        m = (l+r)//2#这里向下取整
        build(l,m,2*rt)
        build(m+1,r,2*rt+1)
        pushup(rt)
    
    build(0,len(num)-1,1)
    
    print(sum_list)

运行结果：  
![这里写图片描述][20180622084704980]  
![这里写图片描述][20180622085156697]  
在二叉树索引中，考虑\[0,12\]是索引1，\[0,6\]是索引2，\[7,12\]是索引3，以此类推。发现sum\_list的打印结果与上图是一一对应的。注意后面没有使用到的完全二叉树节点，就全为0，而这些节点都没有用到。  
分析：sum\_list的0索引不用，第一个数必为0.

# 线段树——单点修改 #

def update(target,add,l,r,rt):#target为目标，add为加的值
        if(l==r):
            sum_list[rt]=sum_list[rt]+add
            return
        m = (l+r)//2
        if(target<=m):
            update(target,add,l,m,2*rt)
        else:
            update(target,add,m+1,r,2*rt+1)
        pushup(rt)
    update(5,7,0,len(num)-1,1)
    print(sum_list)

运行结果：  
![这里写图片描述][20180622090044474]  
![这里写图片描述][20180622090511359]  
分析：第一次调用时，update函数的后三个参数与build函数一样。程序想让num\[5\]+=7，但是实际上只需要修改，\[5\],\[4,5\],\[4,6\],\[0,6\],\[0,12\]这五个区间的sum就行，这里也体现出只需要log n的复杂度。

# 线段树——查询sum #

def quary(L,R,l,r,rt):
        if( (L<=l) and (r<=R)):
            return sum_list[rt]
        m = (l+r)//2
        count = 0
        #分为两个区间[l,m][m+1,r]
        if(L<=m):
            count+=quary(L,R,l,m,2*rt)
        if(R>=m+1):
            count+=quary(L,R,m+1,r,2*rt+1)
        return count
    
    print(quary(1,11,0,len(num)-1,1))

运行结果：![这里写图片描述][70]  
分析：程序想统计\[1,11\]区间内的总和，实际上加和\[1\],\[2,3\],\[4,6\],\[7,9\],\[10,11\]，也就是36=2+7+13+7+7，计算五个数就可以算出\[1,11\]区间内的总和。

[Link 1]: https://blog.csdn.net/zearot/article/details/52280189
[201806220836385]: /images/20220522/cec6d55f51fb4b85af19b4b5c9250138.png
[20180622083924438]: /images/20220522/bca98de988f5402f9220e1f3a25ce19f.png
[2018062208413153]: /images/20220522/f127b75e2ea246b3939ea13d1cf582ee.png
[20180622084704980]: /images/20220522/e52ca10e5e7d45349a88e311f05c64a5.png
[20180622085156697]: /images/20220522/5dc1ffe886a24bc5bad1c2260f1a179a.png
[20180622090044474]: /images/20220522/e5ddfa5e896f44f59061438335873d7c.png
[20180622090511359]: /images/20220522/97057c95cb004ce8aff6bdf091b827cd.png
[70]: /images/20220522/3123b74cc91f4412af607b1e58fb0113.png