首页 > 代码库 > 讲解——线段树

讲解——线段树

                                                                         讲解——线段树

O、引例

A.给出n个数,n<=100,和m个询问,每次询问区间[l,r]的和,并输出。

一种回答:这也太简单了,O(n)枚举搜索就行了。

另一种回答:还用得着o(n)枚举,前缀和o(1)就搞定。

那好,我再修改一下题目。

B.给出n个数,n<=100,和m个操作,每个操作可能有两种:1、在某个位置加上一个数;2、询问区间[l,r]的和,并输出。

回答:o(n)枚举。

动态修改最起码不能用静态的前缀和做了。

好,我再修改题目:

C.给出n个数,n<=1000000,和m个操作,每个操作可能有两种:1、在某个位置加上一个数;2、询问区间[l,r]的和,并输出。

回答:o(n)枚举绝对超时。

那怎么办?这就需要一种强大的数据结构:线段树

一、基本概念

1、线段树是一棵二叉搜索树,它储存的是一个区间的信息。

2、每个节点以结构体的方式存储,结构体包含以下几个信息:

     区间左端点、右端点;(这两者必有)

     这个区间要维护的信息(事实际情况而定,数目不等)。

3、线段树的基本思想:二分

4、线段树一般结构如图所示:

技术分享

5、特殊性质:

由上图可得,

1、每个节点的左孩子区间范围为[l,mid],右孩子为[mid+1,r]

2、对于结点k,左孩子结点为2*k,右孩子为2*k+1,这符合完全二叉树的性质

二、线段树的基础操作

注:以下基础操作均以引例中的求和为例,结构体以此为例:

struct node
{
       int l,r,w;//l,r分别表示区间左右端点,w表示区间和
}tree[4*n+1];

线段树的基础操作主要有5个:

建树、单点查询、单点修改、区间查询、区间修改。

1、建树,即建立一棵线段树

   ① 主体思路:a、对于二分到的每一个结点,给它的左右端点确定范围。

                     b、如果是叶子节点,存储要维护的信息。

                     c、状态合并。

  ②代码

void build(int l,int r,int k)
{
    tree[k].l=l;tree[k].r=r;
    if(l==r)//叶子节点 
    {
        scanf("%d",&tree[k].w);
        return ; 
    }
    int m=(l+r)/2;
    build(l,m,k*2);//左孩子 
    build(m+1,r,k*2+1);//右孩子 
    tree[k].w=tree[k*2].w+tree[k*2+1].w;//状态合并,此结点的w=两个孩子的w之和 
}

③注意

 a.结构体要开4倍空间,具体原因还未搞懂,记住就好了。

 b.千万不要漏了return语句,因为到了叶子节点不需要再继续递归了。

2、单点查询,即查询一个点的状态,设待查询点为x

   ①主体思路:与二分查询法基本一致,如果当前枚举的点左右端点相等,即叶子节点,就是目标节点。如果不是,因为这是二分法,所以设查询位置为x,当前结点区间范围为了l,r,中点为         mid,则如果x<=mid,则递归它的左孩子,否则递归它的右孩子

   ②代码

void ask(int k)
{
    if(tree[k].l==tree[k].r) //当前结点的左右端点相等,是叶子节点,是最终答案 
    {
        ans=tree[k].w;
        return ;
    }
    int m=(tree[k].l+tree[k].r)/2;
    if(x<=m) ask(k*2);//目标位置比中点靠左,就递归左孩子 
    else ask(k*2+1);//反之,递归右孩子 
}

  ③正确性分析:

     因为如果不是目标位置,由if—else语句对目标位置定位,逐步缩小目标范围,最后一定能只到达目标叶子节点。

3、单点修改,即更改某一个点的状态。用引例中的例子,对第x个数加上y

①主体思路

 结合单点查询的原理,找到x的位置;根据建树状态合并的原理,修改每个结点的状态。

技术分享

 ②代码

void add(int k)
{
    if(tree[k].l==tree[k].r)//找到目标位置 
    {
        tree[k].w+=y;
        return;
    }
    int m=(tree[k].l+tree[k].r)/2;
    if(x<=m) add(k*2);
    else add(k*2+1);
    tree[k].w=tree[k*2].w+tree[k*2+1].w;//所有包含结点k的结点状态更新 
}

4、区间查询,即查询一段区间的状态,在引例中为查询区间[x,y]的和

①主体思路

 技术分享

②代码

sum(int k)
{
    if(tree[k].l>=x&&tree[k].r<=y) 
    {
        ans+=tree[k].w;
        return;
    }
    int m=(tree[k].l+tree[k].r)/2;
    if(x<=m) sum(k*2);
    if(y>m) sum(k*2+1);
}

③正确性分析

情况1,3不用说,对于情况2,最差情况是搜到叶子节点,此时一定满足情况1

5、区间修改,时间原因,日后再补上

现在再回到引例中的问题

先输入n,再输入n个数,

再输入m,

再输入m个询问,询问格式:p,x,y

p=1,表示第x个数+y

p=2,表示查询并输出区间[x,y]的和

p=3,查询并输出点x的值

代码如下

#include<cstdio>
using namespace std;
int n,m,p,x,y,ans;
struct node
{
    int l,r,w;
}tree[200001];
inline void build(int l,int r,int k)
{
    tree[k].l=l;tree[k].r=r;
    if(l==r)//叶子节点 
    {
        scanf("%d",&tree[k].w);
        return ; 
    }
    int m=(l+r)/2;
    build(l,m,k*2);//左孩子 
    build(m+1,r,k*2+1);//右孩子 
    tree[k].w=tree[k*2].w+tree[k*2+1].w;//此结点的w=两个孩子的w之和 
}
inline void add(int k)
{
    if(tree[k].l==tree[k].r)//找到目标位置 
    {
        tree[k].w+=y;
        return;
    }
    int m=(tree[k].l+tree[k].r)/2;
    if(x<=m) add(k*2);
    else add(k*2+1);
    tree[k].w=tree[k*2].w+tree[k*2+1].w;//所有包含结点k的结点状态更新 
}
inline void ask(int k)
{
    if(tree[k].l==tree[k].r) //当前结点的左右端点相等,是叶子节点,是最终答案 
    {
        ans=tree[k].w;
        return ;
    }
    int m=(tree[k].l+tree[k].r)/2;
    if(x<=m) ask(k*2);//目标位置比中点靠左,就递归左孩子 
    else ask(k*2+1);//反之,递归右孩子 
}
inline void sum(int k)
{
    if(tree[k].l>=x&&tree[k].r<=y) 
    {
        ans+=tree[k].w;
        return;
    }
    int m=(tree[k].l+tree[k].r)/2;
    if(x<=m) sum(k*2);
    if(y>m) sum(k*2+1);
}
int main()
{
    scanf("%d",&n);
    build(1,n,1);
    scanf("%d",&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&p,&x,&y);
        ans=0;
        if(p==1) add(1);
        else if(p==2)
        {
            sum(1);
            printf("%d\n",ans);
        }
        else
        {
            ask(1);
            printf("%d\n",ans);
        }
    }
}

三、参考题目

1、codevs1080线段树练习 http://codevs.cn/problem/1080/

未完待续

讲解——线段树