Go实现动态开点线段树

技术分享 11个月前 (02-26) 0 999+

关注

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 }