Go实现动态开点线段树

SL88poT0q

1、线段树介绍

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

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

一个节点需要记录它的左子节点、右子节点、当前节点表示的区间的和val，以及暂未下推给子节点的懒惰值lazy。
type SegTreeNode struct {        lazy  int        val   int        left  *SegTreeNode        right *SegTreeNode}2、线段树的创建

整个线段树只需要记录一个根节点以及该线段树表示的区间上届。
type SegTree struct {        //线段树的范围，0~N        N    int        root *SegTreeNode}// 创建线段树func CreateSegTree(n int) *SegTree {        return &SegTree{                N: n,                root: &SegTreeNode{                        lazy:  0,                        val:   0,                        left:  nil,                        right: nil,                },        }}3、递归上推

当更新完了子节点后，回到当前节点的时候，需要更新当前节点的值，表示从树的底部上推值。
// 递归上推func (ST *SegTree) Pushup(node *SegTreeNode) {        node.val = node.left.val + node.right.val}4、懒惰下推

当需要缩小查找区间的时候，需要向下查找，这时候要先把懒惰值下推，防止查找出错误的结果，也防止子节点还未创建。
// 同步下推func (ST *SegTree) Pushdown(node *SegTreeNode, leftnum, rightnum int) {        //创建左右节点        if node.left == nil {                node.left = new(SegTreeNode)        }        if node.right == nil {                node.right = new(SegTreeNode)        }        //下推节点懒惰标记        if node.lazy == 0 {                return        }        node.left.val += leftnum * node.lazy        node.right.val += rightnum * node.lazy        //下推        node.left.lazy += node.lazy        node.right.lazy += node.lazy        //置零        node.lazy = 0}首先先创建左右节点，如果没有需要下推的懒惰标记则直接返回。否则就更新左右节点的val和lazy。
5、更新操作

// 更新操作，更新[left,right]区间的值，start和end是当前处在区间func (ST *SegTree) Update(node *SegTreeNode, start, end, left, right, val int) {        if left <= start && end <= right {                //锁定区间，进行更新                node.val += (end - start + 1) * val                node.lazy += val                return        }        //缩小区间        mid := (start + end) / 2        //需要找到子节点，先下推懒惰标记        ST.Pushdown(node, mid-start+1, end-mid)        if mid >= left {                ST.Update(node.left, start, mid, left, right, val)        }        if mid+1 <= right {                ST.Update(node.right, mid+1, end, left, right, val)        }        //递归        ST.Pushup(node)}left和right表示要更新的区间，而start和end表示当前区间。如果当前区间处在需要更新的区间内，则直接更新区间值以及懒惰值，然后直接返回即可，此时不需要继续更新下面节点的值，这是动态开点的关键所在。
若当前区间并未完全处在需要更新的区间内，则二分该区间，缩小范围进行更新。
例如在一次操作需要更新的是[30,40]范围的值，而当前区间处在[25,50]中，当前区间并未完全处在更新区间，则二分为[25,37]和[38,50]，左区间和右区间均和需要更新的区间存在交集，那么就往下更新，直到更新区间包含当前区间。
在更新完后，进行一次上推。
6、查询操作

与更新操作类似，只需要一个ans来记录答案并且返回。
// 查询操作，返回区间的值func (ST *SegTree) Query(node *SegTreeNode, start, end, left, right int) int {        if left <= start && end <= right {                return node.val        }        mid := (start + end) / 2        ST.Pushdown(node, mid-start+1, end-mid)        ans := 0        if left <= mid {                ans += ST.Query(node.left, start, mid, left, right)        }        if mid+1 <= right {                ans += ST.Query(node.right, mid+1, end, left, right)        }        return ans}3、尝试题目

LeetCode我的日程表安排I
[LeetCode我的日程表安排III](732. 我的日程安排表 III - 力扣（LeetCode）)
2502. 设计内存分配器 - 力扣（LeetCode）