Go实现动态开点线段树
1、线段树介绍线段树是一种用于高效处理区间查询和区间更新的数据结构，当我们需要解决一个频仍更新区间值的问题的时间，就可以采用线段树的结构进行解决。线段树的核心思想是将区间分为多个子区间进行管理，越往下区间范围越小，根节点表示整个线段树能表示的区间。
本文记载使用Go实现动态开点线段树的方式，该模板的线段树用于解决区间求和问题，另有求解区间最小值、最大值的线段树可以进行微调修改即可。
区间查询、区间更新的时间复杂度均为O(logN)。
2、动态开点线段树实现
动态开点的核心在于，需要缩小范围，即进入子节点的时间再进行创建，相对于使用数组来实现线段树，可以更大的减小空间开销。
1、线段树节点
一个节点需要记载它的左子节点、右子节点、当前节点表示的区间的和val，以及暂未下推给子节点的懒惰值lazy。
type SegTreeNode struct {
lazyint
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、更新操作
// 更新操作，更新区间的值，start和end是当前处在区间func (ST *SegTree) Update(node *SegTreeNode, start, end, left, right, val int) { if left
页:
[1]