阿酷尔工作室

V1

2022/03/11阅读:47主题:默认主题

线段树

线段树(segment tree)

什么是线段树

线段树是一种二叉搜索树,什么叫做二叉搜索树,首先满足二叉树,每个结点度小于等于二,即每个结点最多有两颗子树,何为搜索,我们要知道,线段树的每个结点都存储了一个区间,也可以理解成一个线段,而搜索,就是在这些线段上进行搜索操作得到你想要的答案。

线段树是建立在线段的基础上,每个结点都代表了一条线段[a,b]。长度为1的线段称为元线段。非元线段都有两个子结点,左结点代表的线段为[a,(a + b) / 2],右结点代表的线段为[((a + b) / 2)+1,b]。

长度范围为[1,L] 的一棵线段树的深度为log (L) + 1。这个显然,而且存储一棵线段树的空间复杂度为O(L)。

线段树支持最基本的操作为插入和删除一条线段。下面以插入为例,详细叙述,删除类似。

将一条线段[a,b] 插入到代表线段[l,r]的结点p中,如果p不是元线段,那么令mid=(l+r)/2。如果b<mid,那么将线段[a,b] 也插入到p的左儿子结点中,如果a>mid,那么将线段[a,b] 也插入到p的右儿子结点中。

插入(删除)操作的时间复杂度为O(logn)。

线段树能解决的问题

线段树的适用范围很广,可以在线维护修改以及查询区间上的最值,求和。更可以扩充到二维线段树(矩阵树)和三维线段树(空间树)。对于一维线段树来说,每次更新以及查询的时间复杂度为O(logN)。

上面说的太官方了,说浅显一点,线段树主要为了处理区间算法的一些问题,比如我们想对一个区间的所有数据进行求和,你可以使用for循环进行,但是每次都使用for循环这种形式进行计算的方式真的太浪费时间了,for循环的时间复杂度为O(N),我们将其替换成线段树就可以将时间复杂度降低到O(

logn)。如果是区间求和线段树的value就是记录当前区间的和左+右,如果是区间求积那么value就是 左*右。一次类推,经过递归之后,只要每个节点都能保证自己是其左子树和右子树的左?右,就可以实现区间的求值,同时也将原来的复杂度O(N)降低为O(logn),这也就是为什么线段树明明添加了更多的内存,确那么受欢迎的原因。

不要带着线段树只是为了解决区间问题的数据结构,事实上,是线段树多用于解决区间问题,并不是线段树只能解决区间问题,首先,我们得先明白几件事情。

线段树创建、查询与更新

定义一个线段树

// 以下线段树主要目的就i事 查询各个值得和
type mergeFunc func(i, j int) int
// SegmentTree 线段树的定义
type SegmentTree struct {
   data, tree, lazy []int            //< data 原数据, tree 各个子节点之和
   left, right          int
   merge           mergeFunc
}

线段树初始化

线段树初始化就是将一个区间从中间"均分",直到不能再分为止,伪代码如下:

if L == R then this = L
else
  build left_child, L, (L+R)/2
  build left_child, (L+R)/2+1, R
if value[left_child] < value[right_child]
  this = left_child else this = right_child

go实现代码

// Init 线段树 初始化
func (st *SegmentTree) Init(nums []int, op mergeFunc) {
   st.merge = op
   data, tree, lazy := make([]intlen(nums)), make([]int4 * len(nums)), make([]int4 * len(nums))
   // 将线段树中中需要存储的数据,存储到data中
   for i := 0; i < len(nums); i ++ {
      data[i] = nums[i]
   }
   st.data, st.tree, st.lazy = data, tree, lazy
   if len(nums) > 0 {
      // 构建线段树
      st.BuildSegmentTree(00 , len(nums) - 1)
   }
}

// BuildSegmentTree 构造线段树
func (st *SegmentTree) BuildSegmentTree(treeIndex, left, right int) {
   // 如果left = right说明已经走到了叶节点
   if left == right {
      st.tree[treeIndex] = st.data[left]
      return
   }

   midTreeIndex, leftTreeIndex, rightTreeIndex := left + (right - left) >> 1, st.LeftChild(treeIndex), st.RightChild(treeIndex)
   st.BuildSegmentTree(leftTreeIndex, left, midTreeIndex)
   st.BuildSegmentTree(rightTreeIndex, midTreeIndex, right)
   // 当前节点的sum值,是左 + 右
   st.tree[treeIndex] = st.merge(st.tree[leftTreeIndex], st.tree[rightTreeIndex])
}

func (st *SegmentTree) LeftChild(index int) int {
   return 2 * index + 1
}

func (st *SegmentTree) RightChild(index int) int {
   return index * 2 + 2
}

线段树的范围查询查询

如果需要查询的范围和当前节点完全匹配时,该方法返回结果,否则更深入地遍历线段树,找到一部分完全匹配的节点。时刻记着,当前节点的值由其左 子树和右子树共同决定

//Query 查询 [left, right]区间的值
func (st *SegmentTree) Query(left, right int) int {
   if len(st.data) > 0 {
      return st.QueryInTree(00len(st.data) - 1, left, right)
   }
   return 0
}

// QueryInTree 在一 treeIndex位根的线段树中 [left .... right]的范围内,搜索区间 [queryLeft...queryRight]的值
func (st *SegmentTree) QueryInTree(treeIndex, left, right, queryLeft, queryRight int) int {
   if left == queryLeft && right == queryRight {
      return st.tree[treeIndex]
   }

   midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, st.LeftChild(treeIndex), st.RightChild(treeIndex)
   // 说明在树右分支
   if queryLeft > midTreeIndex {
      return st.QueryInTree(rightTreeIndex, midTreeIndex+1, right, queryLeft, queryRight)
   } else if queryRight <= midTreeIndex {
      return st.QueryInTree(leftTreeIndex, left, midTreeIndex, queryLeft, queryRight)
   }
   // 返回 左 + 右
   return st.merge(st.QueryInTree(leftTreeIndex, left, midTreeIndex, queryLeft, midTreeIndex),
      st.QueryInTree(rightTreeIndex, midTreeIndex+1, right, midTreeIndex+1, queryRight))
}

懒查询

与懒查询对应的是懒更新,或者说两者是配套使用的。当区间更新时,并不是使用递归对区间所有的值进行更新,而是把区间内节点增减的变化的值存储到lazy数组中去,等下次查询时再把增减少应用到具体的节点上。这样做是为了分摊时间复杂度,保证查询和更新的时间复杂度在O(logn)级别,不会退化到O(n)级别

懒查询步骤:

  1. 先判断当前节点是否是懒节点。通过lazy[i]是否为0判断。如果是懒节点,将它的增减变化应用到节点上。并更新它的孩子节点,这一步骤和更新操作的第一步完全一样;
  2. 递归查询子节点,以找到适合的查询节点
// QueryLazy 函数
// 查询 [left....right] 区间内的值
func (st *SegmentTree) QueryLazy(left, right int) int {
   if len(st.data) > 0 {
      return st.QueryLazyInTree(00len(st.data)-1, left, right)
   }
   return 0
}

// QueryLazyInTree treeIndex 查询的根节点,[left,right] 被查询区间, [queryLeft, queryRight]需要去查询的区间
func (st *SegmentTree) QueryLazyInTree(treeIndex, left, right, queryLeft, queryRight int) int {
   midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, st.LeftChild(treeIndex), st.RightChild(treeIndex)
   // 看需要查询的区间是否在被查询区间内
   if left > queryRight || right < queryLeft {
      // 如果查询位置超越实际区间,直接放回0
      return 0 // represents a null node
   }
   // 当对应节点的lazy值非空,说明该节点使用了懒查询和懒更新
   if st.lazy[treeIndex] != 0 { // this node is lazy
      for i := 0; i < right-left+1; i++ {
         // 当前tree节点值,+ 所有子节点的lazy和
         st.tree[treeIndex] = st.merge(st.tree[treeIndex], st.lazy[treeIndex])
      }
      // 将lazy值想子节点传递
      if left != right { // update lazy[] for children nodes
         st.lazy[leftTreeIndex] = st.merge(st.lazy[leftTreeIndex], st.lazy[treeIndex])
         st.lazy[rightTreeIndex] = st.merge(st.lazy[rightTreeIndex], st.lazy[treeIndex])
      }
      // 处理完成之后,当前节点不再是懒节点
      st.lazy[treeIndex] = 0 // current node processed. No longer lazy
   }
   // 如果当前区间在查询区间的内部,直接放回当前区间的tree值即可
   if queryLeft <= left && queryRight >= right { // segment completely inside range
      return st.tree[treeIndex]
   }
   // 全部在右半部分
   if queryLeft > midTreeIndex {
      return st.QueryLazyInTree(rightTreeIndex, midTreeIndex+1, right, queryLeft, queryRight)
   } else if queryRight <= midTreeIndex {
      // 全部在右半部分
      return st.QueryLazyInTree(leftTreeIndex, left, midTreeIndex, queryLeft, queryRight)
   }
   // 如果中线两边都有,则按照中线  进行 左 + 右
   // merge query results
   return st.merge(st.QueryLazyInTree(leftTreeIndex, left, midTreeIndex, queryLeft, midTreeIndex),
      st.QueryLazyInTree(rightTreeIndex, midTreeIndex+1, right, midTreeIndex+1, queryRight))
}

单点更新

单点更新是直接对树的叶子节点进行更新,并通过由叶->根的顺序将影响逐步传递到根节点

// Update 更新树节点
func (st *SegmentTree) Update(index, val int) {
   if len(st.data) > 0 {
      st.UpdateInTree(00len(st.data)-1, index, val)
   }
}

// UpdateInTree 以 treeIndex 为根,更新 index 位置上的值为 val
func (st *SegmentTree) UpdateInTree(treeIndex, left, right, index, val int) {
   // 找到节点
   if left == right {
      st.tree[treeIndex] = val;
      return
   }
   midTreeIndex, leftTreeIndex, rightTreeIndex := left+(right-left)>>1, st.LeftChild(treeIndex), st.RightChild(treeIndex)
   // 如果index在右子树
   if index > midTreeIndex {
      st.UpdateInTree(rightTreeIndex, midTreeIndex + 1, right, index, val)
   } else {
      // 如果index在左子树
      st.UpdateInTree(leftTreeIndex, left, midTreeIndex, index, val)
   }
   // 退出程序之前将所有涉及到的节点值都更新下
   st.tree[treeIndex] = st.merge(st.tree[leftTreeIndex], st.tree[rightTreeIndex])
}

区间更新

更新[updateLeft, updateRight]区间的值,这里的更新在区间值原有的基础上增加或者减少值,而不是把区间的值都赋值为x,区间更新关注的是变化,单点更新关注的是定值。当然区间跟新也可以是定值,这里暂且不讨论这种情况。

线段树对单个节点的更新非常有效,时间复杂度为O(logn),要是更新一系列的元素就需要每个元素都单独更新下。这就造成根节点被多次更新就行了重复计算。在图中根节点被更新了3次,82节点被更新了两次,最差的情况是查询到节点不需要更新,但同样需要更新节点的值。添加lazy节点就能避免这种不必要的更新。

使用一个数组lazy,代表惰性节点,当访问或者查询该节点时,该节点就存储对应tree[i]节点增加或者减少的数量,当lazy[i]为0时代表对应节点为非惰性节点,并不需要更新,只有惰性节点才需要更新tree[i]的值。

更新区间节点的步骤:

  1. 判断当前节点是否是懒节点,通过lazy[i]的值进行判断,如果是懒节点,那么将增减变换作用到该节点上,并且更新它的孩子节点
  2. 如果当前节点代表的区域位于更新范围内,则将当前更新操作作用于当前节点
  3. 递归更新子节点
// UpdateLazy 区间更新函数定义
func (st *SegmentTree) UpdateLazy(updateLeft, updateRight, val int) {
   if len(st.data) > 0 {
      st.UpdateLazyInTree(00len(st.data)-1, updateLeft, updateRight, val)
   }
}

分类:

后端

标签:

后端

作者介绍

阿酷尔工作室
V1

恒生研究院