ToB企服应用市场:ToB评测及商务社交产业平台

标题: Go实现动态开点线段树 [打印本页]
作者: 雁过留声    时间: 4 天前
标题: 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



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4