Schwarzeni

191
文章
7
分类
64
标签

线段树学习笔记

慕课网数据结构课程笔记

基础概念

一段区间，比如

  • 区间染色，每次选一段进行染色，问最后可以看到几种颜色
    • 染色操作（更新区间）
    • 查询操作（查询区间）
  • 基于区间的统计查询
    • 2017年注册用户中消费最高的用户？消费最少的用户

基于数组实现的，时间复杂度为 O(n)；基于线段树的实现，为 O(logn)

特性：

  • 更新：更新区间中一个元素或者一个区间的值
  • 查询：一个区间的最大值、最小值，或者区间数字和
  • 线段树不考虑添加元素

结构

1
2
3
4
5
6
7
8
9
10
11
12
13
                  +-----------+
               +--+  0 ... 7  +--+
               |  +-----------+  |
           +---+----+     +------+-+
        +--+ 0 .. 3 +-+   | 4 .. 7 +-----+
        |  +--------+ |   +--------+     |
   +----+--+  +-------+  +-------+ | +---+---+
 +-+ 0..1  |  | 2..3  |  | 4..5  +-+ | 6..7  |
 | +-----+-+  ++-----++  +-+----++   +--+----+
 |       |     |     |     |    |       |    |
++-+  +--+  +--++  +-+-+ +-+-+ ++--+ +--++  ++--+
|0 |  |1 |  | 2 |  | 3 | | 4 | |5  | |6  |  |7  |
+--+  +--+  +---+  +---+ +---+ +---+ +---+  +---+

线段树不一定是完全二叉树，但是一定是平衡二叉树

大小：最多 4n 的空间，例如下图

1
2
3
4
5
6
7
8
9
10
11
12
13
                  +-----------+
               +--+  0 ... 4  +--+
               |  +-----------+  |
           +---+----+     +------+-+
        +--+ 0 .. 1 +-+   | 2 .. 4 +-----+
        |  +--------+ |   +--------+     |
   +----+--+  +-------+  +-------+ | +---+---+
 +-+    0  |  |    1  |  | 2     +-+ | 3..4  |
 | +-----+-+  ++-----++  +-+----++   +--+----+
 |       |     |     |     |    |       |    |
++-+  +--+  +--++  +-+-+ +-+-+ ++--+ +--++  ++--+
|  |  |  |  |   |  |   | |   | |   | |3  |  |4  |
+--+  +--+  +---+  +---+ +---+ +---+ +---+  +---+

样例代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
package main

import "fmt"

type SegmentTree struct {
  data      []int
  tree      []int
  mergeFunc func(lv, rv int) int
}

func NewSegmentTree(data []int, mergeFunc func(lv, rv int) int) *SegmentTree {
  st := &SegmentTree{}
  st.tree = make([]int, 4*len(data))
  st.data = make([]int, len(data))
  st.mergeFunc = mergeFunc
  copy(st.data, data)
  st.buildSegmentTree(0, 0, len(data)-1)
  return st
}

func (st *SegmentTree) Get(i int) int {
  return st.data[i]
}

func (st *SegmentTree) Size() int {
  return len(st.data)
}

// Search 查询 [lIdx, rIdx] 区间的信息
func (st *SegmentTree) Search(lIdx, rIdx int) int {
  return st.search(0, 0, len(st.data)-1, lIdx, rIdx)
}

func (st *SegmentTree) search(root, l, r, lIdx, rIdx int) (res int) {
  if l == lIdx && r == rIdx {
    return st.tree[root]
  }
  lTreeIdx := st.leftChild(root)
  rTreeIdx := st.rightChild(root)
  mid := l + (r-l)/2
  if rIdx <= mid {
    return st.search(lTreeIdx, l, mid, lIdx, rIdx)
  }
  if lIdx > mid {
    return st.search(rTreeIdx, mid+1, r, lIdx, rIdx)
  }
  return st.mergeFunc(
    st.search(lTreeIdx, l, mid, lIdx, mid),
    st.search(rTreeIdx, mid+1, r, mid+1, rIdx))
}

// Update 更新下标为 idx 的值为 val
func (st *SegmentTree) Update(idx int, val int) {
  st.update(0, 0, len(st.data)-1, idx, val)
}

func (st *SegmentTree) update(root, l, r int, idx int, val int) {
  if l == idx && l == r {
    st.tree[root] = val
    st.data[idx] = val
    return
  }
  lTreeIdx := st.leftChild(root)
  rTreeIdx := st.rightChild(root)
  mid := l + (r-l)/2
  if idx <= mid {
    st.update(lTreeIdx, l, mid, idx, val)
  } else {
    st.update(rTreeIdx, mid+1, r, idx, val)
  }
  st.tree[root] = st.mergeFunc(st.tree[lTreeIdx], st.tree[rTreeIdx])
}

// buildSegmentTree 在 root 的位置创建区间为 [l, r] 的线段树
func (st *SegmentTree) buildSegmentTree(root, l, r int) {
  if l == r {
    st.tree[root] = st.data[l]
    return
  }
  lTreeIdx := st.leftChild(root)
  rTreeIdx := st.rightChild(root)
  midIdx := l + (r-l)/2
  st.buildSegmentTree(lTreeIdx, l, midIdx)
  st.buildSegmentTree(rTreeIdx, midIdx+1, r)
  st.tree[root] = st.mergeFunc(st.tree[lTreeIdx], st.tree[rTreeIdx])
}

func (st *SegmentTree) leftChild(idx int) int {
  return 2*idx + 1
}

func (st *SegmentTree) rightChild(idx int) int {
  return 2*idx + 2
}

func main() {
  sg := NewSegmentTree([]int{-2, 0, 3, -5, 2, -1, 10, 23},
    func(lv, rv int) int { return lv + rv })
  fmt.Println(sg.tree)
  fmt.Println(sg.data)
  fmt.Println(sg.Search(1, 6))
  fmt.Println(sg.Search(3, 4))
  sg.Update(3, 5)
  fmt.Println(sg.tree)
  fmt.Println(sg.data)
  fmt.Println(sg.Search(1, 6))
  fmt.Println(sg.Search(3, 4))
}

高级操作

如果将某个区间中的元素都加+3，可以使用懒惰更新，先用一个数组记录未更新的部分，到下次访问的时候在进行更新、

二、三维线段树

使用链表表示线段树

动态创建线段树：一开始深度为1，随着查询区间的增加，树的深度加深

树状数组

Range Minimum Query