[蓝桥杯学习] 线段树

学习blibli

定义

线段树是一种特殊的平衡二叉查找树，使用线段树，可以实现数据的添加、查找和删除。

树的根结点表示了一个完整的单元区间，左右孩子的区间是将父结点的区间进行二分，左右孩子的区间之和，就是他们的根结点。

叶子结点是区间间隔为1的单位区间（存放的是单个数字），当区间[a,b]的a=b时，就是叶子结点了。

如果用线段树来存储一个区间 [a,b]，叶结点的个数就是(b-a+1)，并且存储数字从a到b

实现方法

由于线段树是一棵平衡二叉树，可以使用一个数组来实现（虽然不是严格意义上的完全二叉树，但是可以为了实现和使用方便，就看成是一棵完全二叉树，不存在的结点在数组里空着就好）。

区间长度为 [0,5] 的线段树，要用到的数组区间是从 a[0] 到 a[2*5+2]，其中一些空间是不存储数据的。

根存储在a[0]

结点 i ，父结点：(i-2)/2，左孩子结点：2*i+1 ，右孩子结点：2*i+2

一个结点的信息包括该结点的 value 以及区间左右端点，通常是不将区间左右端点显示地表示出来，因为可以在查找中计算出来。

应用示例

示例：线段树中，结点值是该区间里的数字个数

如果添加数字3，从区间[0,5] 和 [3,5] [3,4] [3,3]对应的结点值都要加1

代码实现

数据插入

//线段树的数据插入
void tree_inset(int pos,int left,int right,int num)
{
    a[pos]++;  //进行要计算的操作
    if(num == left && num == right) return;  //找到数字所在的叶子
    int mid = (left + right)>>1;
    //把num和mid进行比较
    if(num <= mid) tree_inset(pos*2+1,left,mid,num);  //到左孩子去
    else tree_inset(pos*2+2,mid+1,right,num);  //到右孩子去
}

对叶子的查找类似于二分查找。

查询

//线段树的数据查询
int tree_search(int pos,int left,int right,int num)
{
    if(num == left && num == right) return a[pos];
    int mid = (left + right)>>1;
    if(num <= mid) return tree_search(pos*2+1,left,mid,num);
    else return tree_search(pos*2+2,mid+1,right,num);
}

打印线段树

//打印线段树
void tree_print(int pos,int left,int right)
{
    cout << '[' << left << ',' << right << ']' << ' ' << a[pos] << '\n';
    if(left == right) return;
    int mid = (left+right)>>1;
    tree_print(pos*2+1,left,mid);
    tree_print(pos*2+2,mid+1,right);
    return;
}