# 常用数据结构Go语言实现

\[TOC]

## 栈

```go
package stack

import (
    "stack/stack"
    "stack/stackwithcapacity"
)

type Stack interface {
    // Push 添加一个元素
    Push(interface{}) bool
    // BatchPush 批量添加
    BatchPush(...interface{}) bool
    // Pop 弹出栈顶元素
    Pop() (interface{}, bool)
    // Top 获取栈顶元素
    Top() (interface{}, bool)
    // Empty 栈为空
    Empty() bool
    // Len 已使用大小
    Len() int
}

// NewStack 创建一个栈
// if cap <= 0 return 无固定容量的栈
// else return 固定容量的栈
func NewStack(cap int) Stack {
    if cap <= 0 {
        return stack.NewStack()
    }
    return stackwithcapacity.NewStack(cap)
}
```

### 基于链表实现的栈

[演示地址](https://www.cs.usfca.edu/~galles/visualization/StackLL.html)

`添加元素`时`v.next = top.next`使新添加节点指向虚拟头节点`top`的下一节点，而后`top.next = v`

![基于链表实现的栈](/files/-Mh2daxdPfslF_Di-twq)

`移除元素`时 记`value = v.value`，将 `top.next = v.next; v.next = nil`

![基于链表实现的栈移除操作](/files/-Mh2daxe4WP4MisTY-Xm)

```go
package stack

import (
    "container/list"
    "sync"
)

type Stack struct {
    lst  *list.List
    lock sync.RWMutex
}

// NewStack 创建一个栈
func NewStack() *Stack {
    return &Stack{lst: list.New()}
}

// Push 元素入栈
func (stk *Stack) Push(val interface{}) bool {
    stk.lock.Lock()
    defer stk.lock.Unlock()
    stk.lst.PushBack(val)
    return true
}

// Pop 元素出栈
func (stk *Stack) Pop() (interface{}, bool) {
    if stk.Empty() {
        return nil, false
    }

    stk.lock.Lock()
    defer stk.lock.Unlock()
    // 移除尾节点
    var v = stk.lst.Remove(stk.lst.Back())
    return v, false
}

// Empty 栈是否为空
func (stk *Stack) Empty() bool {
    return stk.Len() == 0
}

// Top 获取栈顶元素
func (stk *Stack) Top() (interface{}, bool) {
    if stk.Empty() {
        return nil, false
    }

    stk.lock.RLock()
    defer stk.lock.RUnlock()
    return stk.lst.Back().Value, true
}

// BatchPush 批量添加
func (stk *Stack) BatchPush(valList ...interface{}) bool {
    stk.lock.Lock()
    defer stk.lock.Unlock()
    for i := 0; i < len(valList); i++ {
        stk.lst.PushBack(valList[i])
    }
    return true
}

// Len 获取栈中元素个数
func (stk *Stack) Len() int {
    return stk.lst.Len()
}
```

### 基于slice实现固定容量的栈

[演示地址](https://www.cs.usfca.edu/~galles/visualization/StackArray.html)

`添加元素`时`arr[top]=value; top++`

![固定容量的栈](/files/-Mh2daxgF4qnXDSfLGhM)

`移除元素`时记`v = arr[top]`, 然后`top--`，`return v`

![固定容量的元素弹出元素](/files/-Mh2daxhb4FFC1bmd0R9)

实现如下

```go
package stackwithcapacity

import "sync"

type Stack struct {
    slice []interface{}
    // 从0开始记
    capacity int
    // 从0开始记
    use  int
    lock sync.RWMutex
}

func NewStack(capacity int) *Stack {
    return &Stack{slice: make([]interface{}, capacity), capacity: capacity - 1, use: 0}
}

// Capacity 栈容量大小
func (stk *Stack) Capacity() int {
    return stk.capacity + 1
}

// Len 栈中元素个数
func (stk *Stack) Len() int {
    return stk.use
}

// Full 栈是否已满
func (stk *Stack) Full() bool {
    return stk.use >= stk.capacity
}

// Push 栈有空间时可添加
func (stk *Stack) Push(val interface{}) bool {
    if stk.Full() {
        return false
    }

    stk.lock.Lock()
    defer stk.lock.Unlock()
    stk.slice[stk.use] = val
    stk.use++
    return true
}

// Usable 计算栈的可用空间
func (stk *Stack) Usable() int {
    var usable = stk.capacity - stk.use
    if usable >= 0 {
        return usable
    }
    stk.use = stk.capacity
    return 0
}

// BatchPush 批量添加
func (stk *Stack) BatchPush(valList ...interface{}) bool {
    if len(valList) > stk.Usable() {
        return false
    }

    stk.lock.Lock()
    defer stk.lock.Unlock()
    for i := 0; i < len(valList); i++ {
        stk.slice[stk.use] = valList[i]
        stk.use++
    }
    return true
}

// Empty 栈是否为空
func (stk *Stack) Empty() bool {
    return stk.use == 0
}

// Pop 弹出元素
func (stk *Stack) Pop() (interface{}, bool) {
    if stk.Empty() {
        return nil, false
    }

    stk.lock.Lock()
    defer stk.lock.Unlock()
    var v = stk.slice[stk.use]
    stk.use--
    return v, true
}

// Top 获取栈顶元素
func (stk *Stack) Top() (interface{}, bool) {
    if stk.Empty() {
        return nil, false
    }

    stk.lock.RLock()
    defer stk.lock.RUnlock()
    return stk.slice[stk.use-1], true
}
```

## 队列

```go
package queue

import (
    "queue/deque"
    "queue/ringqueue"
)

type Deque interface {
    Len() int
    Head() interface{}
    Tail() interface{}
    Empty() bool
    LAppend(x interface{}) bool
    Append(x interface{}) bool
    LPop() (interface{}, bool)
    Pop() (interface{}, bool)
}

// NewDeque
// 如果指定了容量则选择循环队列
// 否则选择双端队列
func NewDeque(cap int) Deque {
    if cap > 0 {
        return ringqueue.NewRingQueue(cap)
    }
    return deque.NewDeque()
}
```

### 双端队列

[演示地址](https://visualgo.net/zh/list)

添加元素

```go
    // 记当前节点的后置节点为n
    n := at.next
    // 处理当前节点和新插入节点e的链接关系
    at.next = e
    e.prev = at
    // 处理新插入节点e和当前节点原后置节点的关系
    e.next = n
    n.prev = e
    e.list = l
     // 链表长度加1
    l.len++
```

移除元素

```go
    // 使当前节点前驱节点指向当前节点的后置节点
    e.prev.next = e.next 
    e.next.prev = e.prev
    e.next = nil // avoid memory leaks
    e.prev = nil // avoid memory leaks
    e.list = nil
    // 链表长度减1
    l.len--
```

```go
package deque

import (
    "container/list"
    "sync"
)

type Deque struct {
    // 队列
    lst  *list.List
    lock sync.RWMutex
}

func NewDeque() *Deque {
    return &Deque{lst: list.New()}
}

// Empty 是否为空
func (dq *Deque) Empty() bool {
    dq.lock.RLock()
    defer dq.lock.RUnlock()
    return dq.lst.Len() == 0
}

// Len 当前队列长度
func (dq *Deque) Len() int {
    return dq.lst.Len()
}

// LAppend 从左边添加元素, return是否添加成功
func (dq *Deque) LAppend(v interface{}) bool {
    dq.lock.Lock()
    defer dq.lock.Unlock()
    var e = dq.lst.PushFront(v)
    return e != nil
}

// LPop 从左边移除元素, return元素值、是否移除成功
func (dq *Deque) LPop() (interface{}, bool) {
    if dq.Empty() {
        return nil, false
    }

    dq.lock.Lock()
    defer dq.lock.Unlock()
    var v = dq.lst.Remove(dq.lst.Front())
    return v, true
}

// Append 从右边添加元素, return是否添加成功
func (dq *Deque) Append(v interface{}) bool {
    dq.lock.Lock()
    defer dq.lock.Unlock()
    var e = dq.lst.PushBack(v)
    return e != nil
}

// Pop 从右边移除元素, return元素值、是否移除成功
func (dq *Deque) Pop() (interface{}, bool) {
    if dq.Empty() {
        return nil, false
    }

    dq.lock.Lock()
    defer dq.lock.Unlock()
    var v = dq.lst.Remove(dq.lst.Back())
    return v, true
}

// Head 获取最左边元素
func (dq *Deque) Head() interface{} {
    return dq.lst.Front()
}

// Tail 获取最右边元素
func (dq *Deque) Tail() interface{} {
    return dq.lst.Back()
}
```

### 环形队列

[演示地址](https://www.cs.usfca.edu/~galles/visualization/QueueArray.html)

在队列未满的时候往尾部`添加元素`时`q.nums[q.rear] = x`，`q.rear = (q.rear + 1) % q.length`rear指针后移一位

在队列已满的时候往队列中添加元素则会被拒绝。

![环形队列添加元素](/files/-Mh2daxj7C2lzf7ecVDP)

如果移除从队首移除元素，那么记`v = q.nums[q.front]; q.front = (q.front + 1) % q.length`

![环形队列移除元素](/files/-Mh2daxkowX3UmakDm2o)

```go
package ringqueue

import (
    "sync"
)

// RingQueue 环形队列
type RingQueue struct {
    front  int           // 指向队列头部第1个有效数据的位置
    rear   int           // 指向队列尾部（即最后1个有效数据）的下一个位置，即下一个从队尾入队元素的位置
    length int           // 队列长度，capacity = length - 1
    nums   []interface{} // 队列元素
    // lock
    lock sync.RWMutex
}

// NewRingQueue 创建一个环形队列
func NewRingQueue(k int) *RingQueue {
    var length = k + 1
    return &RingQueue{
        length: length,
        nums:   make([]interface{}, length),
    }
}

func (q *RingQueue) Capacity() int {
    return q.length - 1
}

// Len 获取队列中元素个数
func (q *RingQueue) Len() int {
    q.lock.RLock()
    defer q.lock.RUnlock()
    if q.front > q.rear {
        return q.rear - q.front + q.length
    }
    return q.rear - q.front
}

// Head 获取队首元素
func (q *RingQueue) Head() interface{} {
    if q.Empty() {
        return nil
    }
    return q.nums[q.front]
}

// Tail 获取队尾元素
func (q *RingQueue) Tail() interface{} {
    if q.Empty() {
        return nil
    }
    var pos int // 其实就是rear-1 //pos = (q.rear - 1 + q.length) % q.length
    if q.rear > 0 {
        pos = q.rear - 1
    } else if q.rear == 0 {
        pos = q.length - 1
    }
    return q.nums[pos]
}

// LAppend 从队首添加元素
func (q *RingQueue) LAppend(x interface{}) bool {
    if q.IsFull() {
        return false
    }

    q.lock.Lock()
    defer q.lock.Unlock()
    if q.front == 0 {
        q.front = q.length - 1
    } else {
        q.front--
    }
    q.nums[q.front] = x
    return true
}

// Append 从队尾添加元素
func (q *RingQueue) Append(x interface{}) bool {
    if q.IsFull() {
        return false
    }

    q.lock.Lock()
    defer q.lock.Unlock()
    q.nums[q.rear] = x
    q.rear++ // q.rear = (q.rear + 1) % q.length // rear指针后移一位
    if q.rear == q.length {
        q.rear = 0
    }
    return true
}

// Pop 从队尾移除元素
func (q *RingQueue) Pop() (interface{}, bool) {
    if q.Empty() {
        return nil, false
    }

    q.lock.Lock()
    defer q.lock.Unlock()
    if q.rear == 0 {
        q.rear = q.length - 1
    } else {
        q.rear--
    }
    // q.rear指向队列尾部（即最后1个有效数据）的下一个位置，即下一个从队尾入队元素的位置
    // 上一个被Pop的元素即为q.rear
    return q.nums[q.rear], true
}

// LPop 从队首添加元素
func (q *RingQueue) LPop() (interface{}, bool) {
    if q.Empty() {
        return nil, false
    }

    q.lock.Lock()
    defer q.lock.Unlock()
    var v = q.nums[q.front]
    if q.front == q.length-1 { // front指针后移一位 // q.front = (q.front + 1) % q.length
        q.front = 0
    } else {
        q.front++
    }
    return v, true
}

// Empty 队列是否为空
func (q *RingQueue) Empty() bool {
    return q.front == q.rear
}

// IsFull 队列是否已满
func (q *RingQueue) IsFull() bool {
    return (q.rear+1)%q.length == q.front
}
```

### 优先队列

[演示地址](https://www.cs.usfca.edu/~galles/visualization/Heap.html)

```go
package priorityqueue

// 参考container/heap/example_pq_test.go

// An Item is something we manage in a priority queue.
type Item struct {
    value    interface{} // The value of the item; arbitrary.
    priority int         // The priority of the item in the queue.
    index    int         // The index of the item in the heap.
}

// A PriorityQueue implements heap.*Item and holds Items.
type PriorityQueue []*Item

// NewPriorityQueue 新建一个优先队列
func NewPriorityQueue(items ...*Item) PriorityQueue {
    return items
}

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    // We want Pop to give us the highest, not lowest, priority so we use greater than here.
    return pq[i].priority > pq[j].priority
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}

func (pq *PriorityQueue) Push(item *Item) {
    n := len(*pq)
    item.index = n
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() *Item {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil  // avoid memory leak
    item.index = -1 // for safety
    *pq = old[0 : n-1]
    return item
}

// update modifies the priority and value of an Item in the queue.
func (pq *PriorityQueue) update(item *Item, value interface{}, priority int) {
    item.value = value
    item.priority = priority
    Fix(pq, item.index)
}

// heap
// Init establishes the heap invariants required by the other routines in this package.
// Init is idempotent with respect to the heap invariants
// and may be called whenever the heap invariants may have been invalidated.
// The complexity is O(n) where n = h.Len().
func Init(h *PriorityQueue) {
    n := h.Len()
    for i := n/2 - 1; i >= 0; i-- {
        down(h, i, n)
    }
}

// Push pushes the element x onto the heap.
// The complexity is O(log n) where n = h.Len().
func Push(h *PriorityQueue, x *Item) {
    h.Push(x)
    up(h, h.Len()-1)
}

// Pop removes and returns the minimum element (according to Less) from the heap.
// The complexity is O(log n) where n = h.Len().
// Pop is equivalent to Remove(h, 0).
func Pop(h *PriorityQueue) *Item {
    n := h.Len() - 1
    h.Swap(0, n)
    down(h, 0, n)
    return h.Pop()
}

// Remove removes and returns the element at index i from the heap.
// The complexity is O(log n) where n = h.Len().
func Remove(h *PriorityQueue, i int) *Item {
    n := h.Len() - 1
    if n != i {
        h.Swap(i, n)
        if !down(h, i, n) {
            up(h, i)
        }
    }
    return h.Pop()
}

// Fix re-establishes the heap ordering after the element at index i has changed its value.
// Changing the value of the element at index i and then calling Fix is equivalent to,
// but less expensive than, calling Remove(h, i) followed by a Push of the new value.
// The complexity is O(log n) where n = h.Len().
func Fix(h *PriorityQueue, i int) {
    if !down(h, i, h.Len()) {
        up(h, i)
    }
}

func up(h *PriorityQueue, j int) {
    for {
        i := (j - 1) / 2 // parent
        if i == j || !h.Less(j, i) {
            break
        }
        h.Swap(i, j)
        j = i
    }
}

func down(h *PriorityQueue, i0, n int) bool {
    i := i0
    for {
        j1 := 2*i + 1
        if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
            break
        }
        j := j1 // left child
        if j2 := j1 + 1; j2 < n && h.Less(j2, j1) {
            j = j2 // = 2*i + 2  // right child
        }
        if !h.Less(j, i) {
            break
        }
        h.Swap(i, j)
        i = j
    }
    return i > i0
}
```

## 并查集

[演示地址](https://www.cs.usfca.edu/~galles/visualization/DisjointSets.html)

![并查集](/files/-Mh2daxm8XQ_u0yChyzj)

`查询元素4`所在集合根节点，在查询过程中进行了路径压缩，查询完所在集合，也会使该节点直接指向集合根节点。

![并查集查询4所在集合根节点](/files/-Mh2daxntPvbfDlAr5PW)

`合并元素6所在集合和元素2所在集合`，最开始找到两个元素各自所在集合的根节点，然后将其中一个集合的根节点指向另一个集合的根节点。

![并查集合并元素6所在集合和元素2所在集合](/files/-Mh2daxoRsxcyuvp_0--)

```go
package disjointsets

type DSU []int

// ConstructorDSU 创建容量为n的并查集
// n指的是并查集中点的个数
func ConstructorDSU(n int) DSU {
    var dsu = make(DSU, n)
    // 初始化时每个节点的根节点就是自身
    for i := 0; i < n; i++ {
        dsu[i] = i
    }
    return dsu
}

// Find 查找a的根节点，并进行路径压缩（注意使用路径压缩的话，独立集合的根结点不能初始化为一个相同值，比如-1）
// 如`dsu[i] = -1`，这样在合并时求解是否存在环的时候所找根节点都会为-1而造成误判
func (dsu DSU) Find(a int) int {
    if dsu[a] != a {
        // 某个节点的根节点不是自身时
        // 路径压缩
        dsu[a] = dsu.Find(dsu[a])
    }
    // 获取到根节点
    return dsu[a]
}

// Union 合并两个集合
// False: 说明已经在一个集合中，无需合并
// True: 合并成功
func (dsu DSU) Union(a, b int) bool {
    var (
        aRoot = dsu.Find(a)
        bRoot = dsu.Find(b)
    )
    // 如果根节点相同说明已经在同一个集合中了
    if aRoot == bRoot {
        return false
    }
    // 将集合a加入到集合b中
    dsu[aRoot] = bRoot
    return true
}
```

## 前缀树

[演示地址](https://www.cs.usfca.edu/~galles/visualization/Trie.html)

![前缀树添加元素](/files/-Mh2daxp7wTtp37GCDU6)

```go
package trie

type Trie interface {
    Insert(string)
    Search(string) bool
    HasPrefix(string) bool
}

// Type 前缀树类型
type Type int32

const (
    // EmHashTrie 哈希前缀树
    EmHashTrie = iota
    // EmListTrie 列表前缀树
    EmListTrie
    // EmArrayTrie 数组前缀树
    EmArrayTrie
)

// NewTrie 创建一个Trie
func NewTrie(t Type) Trie {
    switch t {
    case EmHashTrie:
        return NewHashTrie()
    case EmListTrie:
        return NewListTrie()
    case EmArrayTrie:
        return NewArrayTrie()
    default:
        // HashTrie较为通用
        return NewHashTrie()
    }
}
```

### ArrayTire

```go
package trie

// ArrayTrie 数组前缀树
type ArrayTrie struct {
    isWord   bool
    children [26]*ArrayTrie
}

var _ Trie = (*ArrayTrie)(nil)

// NewArrayTrie new arrayTrie
func NewArrayTrie() *ArrayTrie {
    return &ArrayTrie{children: [26]*ArrayTrie{}}
}

// Insert 往前缀树中添加一个元素word
func (a *ArrayTrie) Insert(word string) {
    var curNode = a
    for i := 0; i < len(word); i++ {
        if curNode.children[word[i]-'a'] == nil {
            curNode.children[word[i]-'a'] = NewArrayTrie()
        }
        curNode = curNode.children[word[i]-'a']
    }
    curNode.isWord = true
}

// Search 查找前缀树中是否元素word
func (a *ArrayTrie) Search(word string) bool {
    var _, has = a.search(word)
    return has
}

func (a *ArrayTrie) search(word string) (*ArrayTrie, bool) {
    var curNode = a
    for i := 0; i < len(word); i++ {
        if curNode.children[word[i]-'a'] == nil {
            return nil, false
        }
        curNode = curNode.children[word[i]-'a']
    }
    return curNode, curNode.isWord
}

// HasPrefix 查询前缀树中是否存在前缀prefix
func (a *ArrayTrie) HasPrefix(prefix string) bool {
    var curNode = a
    for i := 0; i < len(prefix); i++ {
        if curNode.children[prefix[i]-'a'] == nil {
            return false
        }
        curNode = curNode.children[prefix[i]-'a']
    }
    return true
}
```

### ListTrie

```go
package trie

// ListTrie 列表前缀树
type ListTrie struct {
    isWord   bool
    char     byte
    children []*ListTrie
}

var _ Trie = (*ListTrie)(nil)

// NewListTrie new listTrie
func NewListTrie() *ListTrie {
    return new(ListTrie)
}

// Insert 往前缀树中添加一个元素word
func (a *ListTrie) Insert(word string) {
    var (
        curNode = a
        tNode   *ListTrie
    )
    for i := 0; i < len(word); i++ {
        if tNode = curNode.find(word[i]); tNode == nil {
            curNode.children = append(curNode.children, &ListTrie{char: word[i]})
        }
        curNode = curNode.find(word[i])
    }
    curNode.isWord = true
}

func (a *ListTrie) find(c byte) *ListTrie {
    for i := 0; i < len(a.children); i++ {
        if a.children[i].char == c {
            return a.children[i]
        }
    }
    return nil
}

// Search 查找前缀树中是否元素word
func (a *ListTrie) Search(word string) bool {
    var _, has = a.search(word)
    return has
}

func (a *ListTrie) search(word string) (*ListTrie, bool) {
    var curNode = a
    for i := 0; i < len(word); i++ {
        curNode = curNode.find(word[i])
        if curNode == nil {
            return nil, false
        }
    }
    return curNode, curNode.isWord
}

// HasPrefix 查询前缀树中是否存在前缀prefix
func (a *ListTrie) HasPrefix(prefix string) bool {
    var curNode = a
    for i := 0; i < len(prefix); i++ {
        curNode = curNode.find(prefix[i])
        if curNode == nil {
            return false
        }
    }
    return true
}
```

### HashTrie

```go
package trie

// HashTrie Hash前缀树
type HashTrie struct {
    isWord   bool
    children map[byte]*HashTrie
}

var _ Trie = (*HashTrie)(nil)

// NewHashTrie new hashTrie
func NewHashTrie() *HashTrie {
    return &HashTrie{children: make(map[byte]*HashTrie)}
}

// Insert 往前缀树中添加一个元素word
func (h *HashTrie) Insert(word string) {
    var curNode = h
    for i := 0; i < len(word); i++ {
        if _, has := curNode.children[word[i]]; !has {
            curNode.children[word[i]] = NewHashTrie()
        }
        curNode = curNode.children[word[i]]
    }
    curNode.isWord = true
}

// Search 查找前缀树中是否元素word
func (h *HashTrie) Search(word string) bool {
    var _, has = h.search(word)
    return has
}

func (h *HashTrie) search(word string) (*HashTrie, bool) {
    var curNode = h
    for i := 0; i < len(word); i++ {
        if curNode.children[word[i]] == nil {
            return nil, false
        }
        curNode = curNode.children[word[i]]
    }
    return curNode, curNode.isWord
}

// HasPrefix 查询前缀树中是否存在前缀prefix
func (h *HashTrie) HasPrefix(prefix string) bool {
    var curNode = h
    for i := 0; i < len(prefix); i++ {
        if curNode.children[prefix[i]] == nil {
            return false
        }
        curNode = curNode.children[prefix[i]]
    }
    return true
}
```

## 线段树

[演示地址](https://visualgo.net/en/segmenttree)

![VisuAlgo - Segment Tree - Max](/files/-Mh2daxr9vDQcmCXGVrB)

```go
package segmenttree

import (
    "errors"
)

var (
    // ErrIndexIllegal 索引非法
    ErrIndexIllegal = errors.New("index is illegal")
)

package segmenttree

// Int64Merger 用户自定义区间内操作逻辑
type Int64Merger func(int64, int64) int64

type Int64Optimization func(int, int, int64) int64

// Int64SegmentTree 线段树
type Int64SegmentTree struct {
    data         []int64
    tree         []int64
    lazy         []int64
    merge        Int64Merger
    optimization Int64Optimization
}

// NewInt64SegmentTree new Int64SegmentTree
func NewInt64SegmentTree(array []int64, merge Int64Merger) *Int64SegmentTree {
    var seg = &Int64SegmentTree{
        data:  array,
        tree:  make([]int64, 4*len(array)),
        lazy:  make([]int64, 4*len(array)),
        merge: merge,
    }
    seg.buildInt64SegmentTree(0, 0, seg.Size()-1)
    return seg
}

// WithInt64Optimization 指定Int64Optimization来自定义区间[left, right]更新value的计算操作
func (s *Int64SegmentTree) WithInt64Optimization(f Int64Optimization) {
    s.optimization = f
}

// leftChild 左子树index
func (s *Int64SegmentTree) leftChild(idx int) int {
    return (idx << 1) + 1
}

// rightChild 右子树index
func (s *Int64SegmentTree) rightChild(idx int) int {
    return (idx << 1) + 2
}

// buildInt64SegmentTree 建立线段树
func (s *Int64SegmentTree) buildInt64SegmentTree(idx int, left int, right int) {
    if left == right {
        s.tree[idx] = s.data[left]
        return
    }
    var (
        leftTreeIdx  = s.leftChild(idx)
        rightTreeIdx = s.rightChild(idx)
        mid          = left + (right-left)/2
    )
    // 创建左子树的线段树
    s.buildInt64SegmentTree(leftTreeIdx, left, mid)
    // 创建右子树的线段树
    s.buildInt64SegmentTree(rightTreeIdx, mid+1, right)
    // merge
    s.tree[idx] = s.merge(s.tree[leftTreeIdx], s.tree[rightTreeIdx])
}

// Size 线段树元素数
func (s *Int64SegmentTree) Size() int {
    return len(s.data)
}

// Get 索引原数组值
func (s *Int64SegmentTree) Get(idx int) (int64, error) {
    if idx < 0 || idx >= s.Size() {
        return 0, ErrIndexIllegal
    }
    return s.data[idx], nil
}

// Query 区间查询
func (s *Int64SegmentTree) Query(queryLeft int, queryRight int) (int64, error) {
    if queryLeft > queryRight {
        queryRight, queryLeft = queryLeft, queryRight
    }
    if queryLeft < 0 || queryRight >= s.Size() {
        return 0, ErrIndexIllegal
    }
    return s.query(0, 0, s.Size()-1, queryLeft, queryRight), nil
}

func (s *Int64SegmentTree) query(idx int, left int, right int, queryLeft int, queryRight int) int64 {
    if left == queryLeft && right == queryRight {
        // 命中所查找区间
        return s.tree[idx]
    }

    var (
        mid = left + (right-left)/2
        // 计算左右子节点下标
        leftIdx  = s.leftChild(idx)
        rightIdx = s.rightChild(idx)
    )
    if queryLeft >= mid+1 {
        // 所查询区间在右半部分
        return s.query(rightIdx, mid+1, right, queryLeft, queryRight)
    }
    if queryRight <= mid {
        // 所查询区间在左半部分
        return s.query(leftIdx, left, mid, queryLeft, queryRight)
    }
    // 所查询区间分布在左右区间
    return s.merge(
        // 查询左部分
        s.query(leftIdx, left, mid, queryLeft, mid),
        // 查询右部分
        s.query(rightIdx, mid+1, right, mid+1, queryRight),
    )
}

// QueryLazy 懒惰查询
func (s *Int64SegmentTree) QueryLazy(queryLeft int, queryRight int) (int64, error) {
    if queryLeft > queryRight {
        queryRight, queryLeft = queryLeft, queryRight
    }
    if queryLeft < 0 || queryRight >= s.Size() {
        return 0, ErrIndexIllegal
    }
    return s.queryLazy(0, 0, s.Size()-1, queryLeft, queryRight), nil
}

func (s *Int64SegmentTree) queryLazy(idx int, left int, right int, queryLeft int, queryRight int) int64 {
    // 处理懒惰更新
    s.pushDown(idx, left, right)

    var (
        mid      = left + (right-left)>>1
        leftIdx  = s.leftChild(idx)
        rightIdx = s.rightChild(idx)
    )
    if left > right || left > queryRight || right < queryLeft {
        return 0
    }
    if queryLeft <= left && right <= queryRight {
        // 在所查找区间范围内
        return s.tree[idx]
    }
    if queryLeft >= mid+1 {
        // 所查询区间在右半部分
        return s.queryLazy(rightIdx, mid+1, right, queryLeft, queryRight)
    }
    if queryRight <= mid {
        // 所查询区间在左半部分
        return s.queryLazy(leftIdx, left, mid, queryLeft, queryRight)
    }
    // 所查询区间分布在左右区间
    return s.merge(
        // 查询左部分
        s.queryLazy(leftIdx, left, mid, queryLeft, mid),
        // 查询右部分
        s.queryLazy(rightIdx, mid+1, right, mid+1, queryRight),
    )
}

// Set 更新元素值
func (s *Int64SegmentTree) Set(index int, e int64) error {
    if index < 0 || index >= s.Size() {
        return ErrIndexIllegal
    }
    // 更新数组元素值
    s.data[index] = e
    // 更新tree元素值
    s.set(0, 0, s.Size()-1, index, e)
    return nil
}

func (s *Int64SegmentTree) set(idx int, left int, right int, index int, e int64) {
    if left == right {
        // 命中节点，更新元素值
        s.tree[idx] = e
        return
    }

    var (
        leftIdx  = s.leftChild(idx)
        rightIdx = s.rightChild(idx)
        mid      = left + (right-left)/2
    )
    if index <= mid {
        // idx在左边
        s.set(leftIdx, left, mid, index, e)
    } else {
        // idx在右边
        s.set(rightIdx, mid+1, right, index, e)
    }
    // merge
    s.tree[idx] = s.merge(s.tree[leftIdx], s.tree[rightIdx])
}

// AddValueLazy
// 给[addLeft....addRight]位置的值都加上value
// 注意这里的更新值是在原来值的基础上增加或者减少，而不是把这个区间内的值都赋值为 x，区间更新和单点更新不同
// 这里的区间更新关注的是变化，单点更新关注的是定值
// 当然区间更新也可以都更新成定值，如果只区间更新成定值，那么 lazy 更新策略需要变化，merge 策略也需要变化，这里暂不详细讨论
func (s *Int64SegmentTree) AddValueLazy(addLeft int, addRight int, value int64) error {
    if addLeft > addRight {
        addRight, addLeft = addLeft, addRight
    }
    if addLeft < 0 || addRight >= s.Size() {
        return ErrIndexIllegal
    }
    s.addValueLazy(0, 0, s.Size()-1, addLeft, addRight, value)
    return nil
}

func (s *Int64SegmentTree) addValueLazy(idx int, left int, right int, addLeft int, addRight int, value int64) {
    // 处理懒惰更新
    s.pushDown(idx, left, right)

    var (
        mid      = left + (right-left)>>1
        leftIdx  = s.leftChild(idx)
        rightIdx = s.rightChild(idx)
    )
    if left > right || left > addRight || right < addLeft {
        return
    }
    if addLeft <= left && right <= addRight {
        // 正好在一个区间内区间
        if s.optimization != nil {
            s.tree[idx] = s.merge(s.tree[idx], s.optimization(left, right, value))
        } else {
            for i := 0; i < right-left+1; i++ {
                s.tree[idx] = s.merge(s.tree[idx], value)
            }
        }
        if left != right {
            s.lazy[leftIdx] = s.merge(s.lazy[leftIdx], value)
            s.lazy[rightIdx] = s.merge(s.lazy[rightIdx], value)
        }
        return
    }
    // 需要分别更新左右区间
    s.addValueLazy(leftIdx, left, mid, addLeft, addRight, value)
    s.addValueLazy(rightIdx, mid+1, right, addLeft, addRight, value)
    s.tree[idx] = s.merge(s.tree[leftIdx], s.tree[rightIdx])
}

func (s *Int64SegmentTree) pushDown(idx int, left int, right int) {
    var (
        leftIdx  = s.leftChild(idx)
        rightIdx = s.rightChild(idx)
    )
    // 处理懒惰更新
    if s.lazy[idx] != 0 {
        if s.optimization != nil {
            s.tree[idx] = s.merge(s.tree[idx], s.optimization(left, right, s.lazy[idx]))
        } else {
            // 懒惰更新根节点 如果是区间和则等同于：s.tree[idx] += (right-left+1)*s.lazy[idx]
            for i := 0; i < right-left+1; i++ {
                s.tree[idx] = s.merge(s.tree[idx], s.lazy[idx])
            }
        }
        if left != right {
            // 懒惰更新子节点 如果是区间求和则等同于：s.lazy[leftIdx] += s.lazy[idx]
            s.lazy[leftIdx] = s.merge(s.lazy[leftIdx], s.lazy[idx])
            s.lazy[rightIdx] = s.merge(s.lazy[rightIdx], s.lazy[idx])
        }
        // 消除懒惰更新标志
        s.lazy[idx] = 0
    }
}
```

## 跳表

```go
package skiplist

type ISkipList interface {
    // Search 查找是否存在target
    Search(target int) bool
    // Add 添加元素
    Add(num int)
    // Erase 移除元素
    Erase(num int) bool
}
```

```go
package skiplist


import (
    "math"
    "math/rand"
    "sync"
)

const (
    headValue = math.MinInt32
)

// SkipList 跳表
type SkipList struct {
    // 虚拟头节点，最高层
    head *node
    // 层级
    level int
    // 链表长度
    length int
    // 锁
    lock sync.RWMutex
}

// 节点
type node struct {
    // 节点值
    val int
    // 右节点
    right *node
    // 下一级
    down *node
}

func NewSkipList() *SkipList {
    var sp = Constructor()
    return &sp
}

func Constructor() SkipList {
    return SkipList{
        // 虚拟头节点
        head: &node{
            val: headValue,
        },         //头节点 设置为一个极小的值
        level:  1, //跳表层数，初始化为1级
        length: 1, //原链表的个数（包括虚拟头节点）
    }
}

// Search 查找是否存在target
// 由于设置了虚拟节点，那么意味着它存在的话，它必然是某个节点的右节点，就是说它前面一定有一个节点
func (s *SkipList) Search(target int) bool {
    s.lock.RLock()
    defer s.lock.RUnlock()
    return s.getBefore(target, s.head) != nil
}

// Add 添加元素
func (s *SkipList) Add(num int) {
    s.lock.Lock()
    defer s.lock.Unlock()
    var (
        n     = s.head
        i     int
        nodes = make([]*node, s.level+1)
    )
    // 从最高层往下查找符合条件的节点
    for n != nil {
        for n.right != nil && n.right.val < num {
            // 直到找到一个节点的下一个节点是大于目标值的
            n = n.right
        }
        nodes[i] = n
        i++
        n = n.down
    }
    // 最后一个i是没有值的要去掉
    i--

    // 最底层链表添加新节点
    var (
        // 原链表的的前值
        beforeNode = nodes[i]
        newNode    = &node{
            val:   num,
            right: beforeNode.right,
        }
    )
    beforeNode.right = newNode
    s.length++

    // 建立索引
    for {
        // 索引建立规则
        if rand.Intn(2) == 0 || s.level > (s.length>>6)+1 {
            break
        }

        if i > 0 {
            // 从底层往上插入目标节点
            i--
            newNode = &node{
                val:   num,
                right: nodes[i].right, // 连接右节点
                down:  newNode,        // 连接下一层
            }
            // 前一节点与目标节点相连
            nodes[i].right = newNode
        } else {
            // 新增层级
            newNode = &node{
                val:  num,
                down: newNode,
                // 改节点是新层级的最后一个节点，因此没有右节点
            }
            // 虚拟节点
            s.head = &node{
                val:   headValue,
                right: newNode, // 向由连接新节点
                down:  s.head,  // 向下连接前一虚拟节点
            }
            s.level++
        }
    }
}

// Erase 移除元素
func (s *SkipList) Erase(num int) bool {
    s.lock.Lock()
    defer s.lock.Unlock()
    var (
        target = num
        before = s.getBefore(target, s.head)
    )
    if before == nil {
        return false
    }

    // 逐级移除节点
    for {
        if before == nil {
            break
        }
        // 移除目标节点
        before.right = before.right.right
        // 降级
        before = before.down
        // 继续寻找下一个满足条件的节点
        before = s.getBefore(num, before)
    }
    s.length--
    return true
}

// 获取目标值的前一个节点
func (s *SkipList) getBefore(target int, from *node) *node {
    var n = from
    for n != nil {
        for n.right != nil && n.right.val < target {
            // 如果n存在右节点
            n = n.right
        }
        if n.right != nil && n.right.val == target {
            // 找到了
            return n
        }
        // 没找到到下一级找
        n = n.down
    }
    // 没找到
    return nil
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://1005281342.gitbook.io/code-porter/shu-ju-jie-gou/ji-zhong-shu-ju-jie-gou-de-go-shi-xian.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.