# Go 主席树 板子

**Repository Path**: hoemfei/chairmanTree

## Basic Information

- **Project Name**: Go 主席树 板子
- **Description**: 静态主席树的实现-可以当板子用
后面会更新动态主席树 
（树状数组套主席树）
- **Primary Language**: Go
- **License**: Zlib
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2022-01-10
- **Last Updated**: 2022-09-23

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Go 静态主席树

#### 介绍
 结构体方式实现的静态主席树

```Go
type Tree struct {        //主席树结构体
	root []*node      //用于存放每棵权值线段树的 "树根"
	index int         //构建树的时候用于根节点下标
}
type node struct {  //"权值线段树节点"的结构体
	sum, l, r int         //sum 值的计数, l, r 表示当前节点的左右区间
	left, right *node     //左右孩子节点
}
```

 频繁查询数据任意区间第K大 第K小   

![静态区间查找](https://images.gitee.com/uploads/images/2022/0110/154021_086b2c66_6507691.png "屏幕截图.png")

```Go
func main() {
    arr := []int{1211, 212134, 172, 966, 111, 111}    //对于值域较大的，建议先离散化
    //BEGIN--->对arr数组离散化
    bak := make([]int, len(arr))    
    copy(bak, arr)
    sort.Ints(bak)         //排序
    unique(&bak)           //去重
    Len:=len(arr)
    myTree := InitTree(Len) //构建主席树，一般开n个空间存储树根即可
    for i:=0; i<Len; i++ {
        myTree.Insert(lower_bound(bak, arr[i]))     //二分查找arr[i] 在bak数组中的下标位置
    }
    //END--->离散化后的数组arr插入到树中
    fmt.Println(bak[myTree.Query(0, 5, 2)]) //查找arr[0-5]区间第2大是谁
    fmt.Println(bak[myTree.Query(1, 3, 1)]) //查找arr[1-3]区间第1大是谁
}
```