Go实现动态开点线段树

1、线段树介绍

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

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

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

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

复制代码

2、线段树的创建

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

1. type SegTree struct {
2.         //线段树的范围，0~N
3.         N    int
4.         root *SegTreeNode
5. }
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. }

复制代码

3、递归上推

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

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

复制代码

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。
5、更新操作

[code]// 更新操作，更新[left,right]区间的值，start和end是当前处在区间func (ST *SegTree) Update(node *SegTreeNode, start, end, left, right, val int) {        if left