【算法狂想曲】数据结构 之 线段树

2020-04-12   112 次阅读


前言

今天在做某个习题集的时候看到了这个概念,就觉得很好玩,于是就去网上学习了一下
线段树,名副其实,相当于“树的每个节点都是一条线段”,可运用于求区间之和

本人学习的线段树教程

理解了线段树的基本原理之后,就打开CodeBlocks写代码了

下图使用 draw.io 绘制
Untitled Diagram.png

基本操作

注意,需要一个原数组N来建立线段树

数据结构

struct lineTree
{
    int l;	//左界
    int r;	//右界
    int sum;	//总和
};

建立

//i为当前节点的下标(因为整个是一个结构数组),l是当前区间的左界,r是当前区间的右界
void build(int i,int l,int r)
{
    line[i].l=l;
    line[i].r=r;

//如果左界等于右界,说明单前节点为单元素,可以直接插入原数组中对应下标的元素
    if(line[i].l==line[i].r)
    {
        line[i].sum=N[l];
        return;
    }
    int mid = (l+r)/2;		//计算中值
    build(i*2,l,mid);		//递归建立,左结点
    build(i*2+1,mid+1,r);	//递归建立,右结点

//当左结点与右节点都完成建立后,计算当前节点的值
    line[i].sum=line[2*i].sum+line[2*i+1].sum;
}

修改(原数组元素发生变化,线段树需要跟着进行变动)

修改的主要目标是找到对应的单元素节点,然后再往回遍历将路途上的各节点值更新

//参数说明: indexA是当前节点的下标,pos是原数组要修改元素的下标,m是修改后的元素值
void modified(int indexA,int pos,int m)
{
  	
    if(line[indexA].l==line[indexA].r)	//找到目标单节点,改变其值
    {
        line[indexA].sum=m;
        return;
    }
//如果目标值在左子区间,遍历左子区间,否则遍历右子区间
    if(pos<=line[indexA*2].r)		
        {
            modified(indexA*2,pos,m);
            line[indexA].sum=line[indexA*2].sum+line[indexA*2+1].sum;   //遍历完成后回来更新当前节点的值,下面同
        }
    else if(pos>=line[indexA*2+1].l)
        {
            modified(indexA*2+1,pos,m);
             line[indexA].sum=line[indexA*2].sum+line[indexA*2+1].sum;
        }
}

查询(寻找某一区间的值)

//参数说明:cur代表当前节点的下标,s代表目标区间的左界,e代表目标区间的右界
int Search(int cur,int s,int e)
{
  //如果当前区间完全被目标区间包含或者与目标区间相同,则直接返回该区间值
    if((s<=line[cur].l)&&(e>=line[cur].r))
    return line[cur].sum;
  //如果当前区间与目标区间毫无关联,返回0
    if(line[cur].l>e||line[cur].r<s)
        return 0;
    int total=0;
//处理有交集但是没有包含的情况,第一个是与左子区间有交集,第二个是与右子区间有交集
    if(line[2*cur].r>=s) total+=Search(cur*2,s,e);
    if(line[2*cur+1].l<=e) total+=Search(cur*2+1,s,e);
    return total;
}

代码测试

创建线段树,并计算特定段的和,修改值后在进行测试

测试代码1

build(1,1,10);
std::cout<<Search(1,1,10)<<std::endl;
modified(1,2,666);
std::cout<<Search(1,1,10)<<std::endl;
modified(1,3,4);
std::cout<<Search(1,1,10)<<std::endl;
modified(1,2,6);
std::cout<<Search(1,1,10)<<std::endl;

测试所用数组元素1,2,3,4,5,6,7,8,9,10

输出结果


55     //1到10的和
719    //1+666+3+4+5+6+7+8+9+10	
720    //1+666+4+4+5+6+7+8+9+10	
60     //1+6+4+4+5+6+7+8+9+10

测试代码2

build(1,1,10);
std::cout<<Search(1,2,8)<<std::endl;
modified(1,2,666);
std::cout<<Search(1,2,3)<<std::endl;
modified(1,3,4);
std::cout<<Search(1,3,7)<<std::endl;
modified(1,2,6);
std::cout<<Search(1,1,6)<<std::endl;

输出结果

35	//2+3+4+5+6+7+8
669	//666+3
26	//4+4+5+6+7
26	//1+6+4+4+5+6

实战

第一次做题进度第二题

总结

线段树还蛮好用的,就是代码数有点多,可能还有更简洁的代码吧

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议