常用数据结构Go语言实现

[TOC]

栈

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)
}

基于链表实现的栈

演示地址

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

基于链表实现的栈

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

基于链表实现的栈移除操作

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实现固定容量的栈

演示地址

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

固定容量的栈

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

固定容量的元素弹出元素

实现如下

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
}

队列

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()
}

双端队列

演示地址

添加元素

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

移除元素

    // 使当前节点前驱节点指向当前节点的后置节点
    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--

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()
}

环形队列

演示地址

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

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

环形队列添加元素

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

环形队列移除元素

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
}

优先队列

演示地址

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
}

并查集

演示地址

并查集

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

并查集查询4所在集合根节点

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

并查集合并元素6所在集合和元素2所在集合

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
}

前缀树

演示地址

前缀树添加元素

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

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

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

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
}

线段树

演示地址

VisuAlgo - Segment Tree - Max

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
    }
}

跳表

package skiplist

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

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
}