template/segment_tree/segment_tree.md · 子安/note_lab

### 线段树(segment tree)

#### 什么是线段树

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

线段树是建立在[线段](https://baike.baidu.com/item/线段)的基础上，每个结点都代表了一条线段[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)，这也就是为什么线段树明明添加了更多的内存，确那么受欢迎的原因。

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

![img](image/-16470083121994.png)

![img](image/-16470083121941.png)

#### 线段树创建、查询与更新

**定义一个线段树**

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

**线段树初始化**

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

```C%2B%2B
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实现代码

```Go
// Init 线段树 初始化
func (st *SegmentTree) Init(nums []int, op mergeFunc) {
   st.merge = op
   data, tree, lazy := make([]int, len(nums)), make([]int, 4 * len(nums)), make([]int, 4 * 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(0, 0 , 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
}
```

**线段树的范围查询查询**

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

![img](image/-16470083121942.png)

```Go
//Query 查询 [left, right]区间的值
func (st *SegmentTree) Query(left, right int) int {
   if len(st.data) > 0 {
      return st.QueryInTree(0, 0, len(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. 递归查询子节点，以找到适合的查询节点

```Go
// QueryLazy 函数
// 查询 [left....right] 区间内的值
func (st *SegmentTree) QueryLazy(left, right int) int {
   if len(st.data) > 0 {
      return st.QueryLazyInTree(0, 0, len(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))
}
```

**单点更新**

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

![img](image/-16470083121953.png)

```Go
// Update 更新树节点
func (st *SegmentTree) Update(index, val int) {
   if len(st.data) > 0 {
      st.UpdateInTree(0, 0, len(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，区间更新关注的是变化，单点更新关注的是定值。当然区间跟新也可以是定值，这里暂且不讨论这种情况。

![img](image/-16470083121953.png)

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

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

更新区间节点的步骤：

1. 判断当前节点是否是懒节点，通过lazy[i]的值进行判断，如果是懒节点，那么将增减变换作用到该节点上，并且更新它的孩子节点
2. 如果当前节点代表的区域位于更新范围内，则将当前更新操作作用于当前节点
3. 递归更新子节点

```Go
// UpdateLazy 区间更新函数定义
func (st *SegmentTree) UpdateLazy(updateLeft, updateRight, val int) {
   if len(st.data) > 0 {
      st.UpdateLazyInTree(0, 0, len(st.data)-1, updateLeft, updateRight, val)
   }
}
```

子安/note_lab

简介

发行版

贡献者

语言

近期动态

子安/note_lab .gitee-modal { width: 500px !important; }

简介

发行版

贡献者

语言

近期动态

搜索帮助

子安/note_lab