# Go 权值线段树_实现板子

**Repository Path**: hoemfei/weightSM

## Basic Information

- **Project Name**: Go 权值线段树_实现板子
- **Description**: Go 实现的权值线段树
- **Primary Language**: Go
- **License**: Zlib
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-01-04
- **Last Updated**: 2022-07-26

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Go 权值线段树_实现板子

#### 介绍
Go 实现的权值线段树
1. 结构体版本 和 数组版本实现
2. 结构体版本可以动态开点，函数func (root *node)insert(val int) 动态开点函数
3. 数组版本速度快，结构体版本，动态开点，不需要离散化

#### 软件架构
![权值线段树插入7个数的图像](https://images.gitee.com/uploads/images/2022/0104/150956_1271bbba_6507691.png "微信图片_20220104150945.png")
软件架构说明



```Go
//无论是结构体版本还是数组版本，main函数通用
func main() {
    arr := []int{1211, 212134, 172, 966, 111}
    //BEGIN->离散化代码
    bak := make([]int, len(arr))
    copy(bak, arr)
    sort.Ints(bak)  //排序
    unique(&bak) //去重
    Len:=len(arr)
    myTree := InitTree(len(bak)-1)  //构建一个空的权值线段树
    for i:=0; i<Len; i++ {
        //END->离散化代码
        myTree.UpDate(lower_bound(bak, arr[i]), 1)    //二分找值映射的下标, 插入到树中
    }
    fmt.Println(bak[myTree.Kth(3)]) //查找第3大
}
```