Go语言实现动态开点线段树详解

微生晓楠

1、线段树介绍

线段树是一种用于高效处理区间查询和区间更新的数据结构，当我们需要解决一个频繁更新区间值的问题的时候，就可以采用线段树的结构进行解决。线段树的核心思想是将区间分为多个子区间进行管理，越往下区间范围越小，根节点表示整个线段树能表示的区间。
本文记录使用Go实现动态开点线段树的方式，该模板的线段树用于解决区间求和问题，还有求解区间最小值、最大值的线段树可以进行微调修改即可。
区间查询、区间更新的时间复杂度均为O(logN)。

2、动态开点线段树实现

动态开点的核心在于，需要缩小范围，即进入子节点的时候再进行创建，相对于使用数组来实现线段树，可以更大的减小空间开销。

线段树节点

一个节点需要记录它的左子节点、右子节点、当前节点表示的区间的和val，以及暂未下推给子节点的懒惰值lazy。

1. type SegTreeNode struct {
   
2.     lazy  int
   
3.     val   int
   
4.     left  *SegTreeNode
   
5.     right *SegTreeNode
   
6. }

复制代码

线段树的创建

整个线段树只需要记录一个根节点以及该线段树表示的区间上届。

1. type SegTree struct {
   
2.     //线段树的范围，0~N
   
3.     N    int
   
4.     root *SegTreeNode
   
5. }
   
6. 
   
7. // 创建线段树
   
8. func CreateSegTree(n int) *SegTree {
   
9.     return &SegTree{
   
10.         N: n,
    
11.         root: &SegTreeNode{
    
12.             lazy:  0,
    
13.             val:   0,
    
14.             left:  nil,
    
15.             right: nil,
    
16.         },
    
17.     }
    
18. }

复制代码

递归上推

当更新完了子节点后，回到当前节点的时候，需要更新当前节点的值，表示从树的底部上推值。

1. // 递归上推
   
2. func (ST *SegTree) Pushup(node *SegTreeNode) {
   
3.     node.val = node.left.val + node.right.val
   
4. }

复制代码

懒惰下推

当需要缩小查找区间的时候，需要向下查找，这时候要先把懒惰值下推，防止查找出错误的结果，也防止子节点还未创建。

1. // 同步下推
   
2. func (ST *SegTree) Pushdown(node *SegTreeNode, leftnum, rightnum int) {
   
3.     //创建左右节点
   
4.     if node.left == nil {
   
5.         node.left = new(SegTreeNode)
   
6.     }
   
7.     if node.right == nil {
   
8.         node.right = new(SegTreeNode)
   
9.     }
   
10.     //下推节点懒惰标记
    
11.     if node.lazy == 0 {
    
12.         return
    
13.     }
    
14.     node.left.val += leftnum * node.lazy
    
15.     node.right.val += rightnum * node.lazy
    
16.     //下推
    
17.     node.left.lazy += node.lazy
    
18.     node.right.lazy += node.lazy
    
19.     //置零
    
20.     node.lazy = 0
    
21. }

复制代码

首先先创建左右节点，如果没有需要下推的懒惰标记则直接返回。否则就更新左右节点的val和lazy。

更新操作

1. // 更新操作，更新[left,right]区间的值，start和end是当前处在区间
   
2. func (ST *SegTree) Update(node *SegTreeNode, start, end, left, right, val int) {
   
3.     if left <= start && end <= right {
   
4.         //锁定区间，进行更新
   
5.         node.val += (end - start + 1) * val
   
6.         node.lazy += val
   
7.         return
   
8.     }
   
9.     //缩小区间
   
10.     mid := (start + end) / 2
    
11.     //需要找到子节点，先下推懒惰标记
    
12.     ST.Pushdown(node, mid-start+1, end-mid)
    
13.     if mid >= left {
    
14.         ST.Update(node.left, start, mid, left, right, val)
    
15.     }
    
16.     if mid+1 <= right {
    
17.         ST.Update(node.right, mid+1, end, left, right, val)
    
18.     }
    
19.     //递归
    
20.     ST.Pushup(node)
    
21. }

复制代码

left和right表示要更新的区间，而start和end表示当前区间。如果当前区间处在需要更新的区间内，则直接更新区间值以及懒惰值，然后直接返回即可，此时不需要继续更新下面节点的值，这是动态开点的关键所在。
若当前区间并未完全处在需要更新的区间内，则二分该区间，缩小范围进行更新。
例如在一次操作需要更新的是[30,40]范围的值，而当前区间处在[25,50]中，当前区间并未完全处在更新区间，则二分为[25,37]和[38,50]，左区间和右区间均和需要更新的区间存在交集，那么就往下更新，直到更新区间包含当前区间。
在更新完后，进行一次上推。

查询操作

与更新操作类似，只需要一个ans来记录答案并且返回。

1. // 查询操作，返回区间的值
   
2. func (ST *SegTree) Query(node *SegTreeNode, start, end, left, right int) int {
   
3.     if left <= start && end <= right {
   
4.         return node.val
   
5.     }
   
6.     mid := (start + end) / 2
   
7.     ST.Pushdown(node, mid-start+1, end-mid)
   
8.     ans := 0
   
9.     if left <= mid {
   
10.         ans += ST.Query(node.left, start, mid, left, right)
    
11.     }
    
12.     if mid+1 <= right {
    
13.         ans += ST.Query(node.right, mid+1, end, left, right)
    
14.     }
    
15.     return ans
    
16. }

复制代码

到此这篇关于Go语言实现动态开点线段树详解的文章就介绍到这了,更多相关Go线段树内容请搜索晓枫资讯以前的文章或继续浏览下面的相关文章希望大家以后多多支持晓枫资讯！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！