线段树[To be continued]

目录

• • • 学姐的blog

---

数据结构--线段树

一、定义

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为n，即整个线段区间的长度。使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为o(logn）。而未优化的空间复杂度为2n，因此有时需要离散化让空间压缩。--百度百科

你们可能会问什么是，我也不知道。

如上图就是一颗[1,8]的线段树。

二、性质

它是一颗二叉树，二叉树的性质它都有。（应该是这样）

三、基本操作

线段树的基础操作主要有5个：建树、单点查询、单点修改、区间查询、区间修改。

0.结构体

struct node{
    int l,r,w;//l，r分别表示区间左右端点，w表示区间和
}tree[maxn*4+1];//注意线段树要开四倍空间。

1.建树

void build(int l,int r,int now){
    tree[now].l=l,tree[now].r=r;//记下now这个节点所表示的区间。
    if(l==r){//左右端点相等，now节点为叶子结点。
        scanf("%d",tree[now].w);//读入叶子结点的值。
        return;//不用进行下面的了。
    }
    int mid=(l+r)>>1;//>>1相当于/2
    build(l,mid,now<<1);//<<1相当于*2
    build(mid+1,r,now<<1|1);//<<1|1相当于*2+1
    tree[now].w=tree[now<<1].w+tree[now<<1|1].w;//更新区间和
}

2.单点查询

询问第x个点的值。

void ask_single(int x,int now){
    if(tree[now].l==tree[now].w){//叶子结点，即最终答案。
        ans=tree[now].w;
        return;
    }
    int mid=(tree[now].l+tree[now].r)>>1;//计算区间的中点。
    if(x<=mid){
        ask_single(x,now<<1);//查找该点的左孩子
    }else{
        ask_single(x,now<<1|1);//查找该点的有孩子
    }
}

3.单点修改

给第x个点加上y。（和单点查询差不多qwq）

void updata_single(int x,int y,int now){
    if(tree[now].l==tree[now].r){
        tree[now].w+=y;
        return;
    }
    int mid=(tree[now].l+tree[now].r)>>1;
    if(x<=mid){
        updata_single(x,y,now<<1);
    }else{
        updata_single(x,y,now<<1|1);
    }
    tree[now].w=tree[now<<1].w+tree[now<<1|1].w;//单点修改后要更新区间和
}

4.区间修改

将某区间每一个数数加上x

5.区间查询

求出某区间每一个数的和

void ask_range(int x,int y,int now){
    if(tree[now].l>=x&&tree[now].r<=y){//[l,r]是[x,y]的子集
        ans+=tree[now].w;
        return;
    }
    int mid=(tree[now].l+tree[now].r)>>1;
    if(x<=mid){
        ask_range(x,y,now<<1);
    }
    if(y>mid){
        ask_range(x,y,now<<1|1);
    }
}//本蒟蒻还不是很会。

四、题目

单点修改、区域查询模板

codevs 1080
洛谷p3374

五、鸣谢

学姐的blog