线段树---从入门到入土

· · 题解

本蒟蒻第一次写文章资瓷一下下啦~~~

线段树是从OI萌新转向OI大佬的重要算法

在实际应用也是可以将O(N）的复杂度优化到O（log N）的神奇东西

进入正题

第一部分---线段树概念（包括前置知识）

线段树是一种二叉树,举个小小de栗子

其实他就是个二分的过程

这是什么意思呢？ 如果你要表示线段的和，那么最上面的根节点的权值表示的是这个线段1~8的和。根的两个儿子分别表示这个线段中1~4的和，与5~8的和。

当然后面的也是一样

由此，我们可以退出一个性质

节点i的权值=她的左儿子权值+她的右儿子权值

我们再来一个前置性知识

假设一个节点编号为n，那么它的左儿子的编号为n<<1 (2*n).

自然右儿子的编号为(n<<1)|1(2*n+1)

千万记住（（n<<1）|1要加括号，不然会先算1|1，再算左移！！！）

so，我们可以struct一个结构体node.l表示它的左儿子，node.r表示它的右儿子，node.sum表示区间和

结合上面的式子，我们可以得tree[i].sum=tree[i2].sum+tree[i2+1].sum;

就有了接下来的代码:

inline void build(int i,int l,int r)
    {//inline加速的，可以不加
    node[i].l=l;node[i].r=r;
    if(l==r)
    {//左右指向一个，说明此时是叶子节点
        node[i].sum=input[l];
        return ;
    }
    int mid=(l+r)>>1;//((l+r)/2)
    build(i*2,l,mid);//建造左子树and右子树
    build(i*2+1,mid+1,r);
    node[i].sum=node[i*2].sum+node[i*2+1].sum;
    //上述性质
    return ;
}

第二部分---线段树入门

线段树中比较常用的一般有:单点修改，区间查询.区间修改，单点查询.以及其衍生出来的许多操作，我在此只讲这两个

2.1 区间修改，单点查询

区间修改:

假设我们需要在l到r这个区间所有数都加上x，那么我们只需要在这个区间置上标记，在单点查询是在在这数组上面把标记加起来就好

具体做法如思路，直接上代码~~~

void node_add(int i,int l,int r,int k)
{
    if(node[i].l>=l && node[i].r<=r)
    {//如果这个区间被完全包括在目标区间里面，在这个区间标记k
        node[i].sum+=k;
        return ;
    }
    if(node[i*2].r>=l)
    node_add(i*2,l,r,k);
    if(node[i*2+1].l<=r)
    node_add(i*2+1,l,r,k);
}

那么单点查询么emm...那就更简单了,直接无脑加标记就好了

void chazhao(int i,int k)
{
   ans+=node[i].num;//又是无脑叠加
    if(node[i].l==node[i].r)
    return ;
    if(k<=node[i*2].r)
   chazhao(i*2,dis);
    if(k>=node[i*2+1].l)
    chazhao(i*2+1,dis);
}

2.2 单点修改，区间查询

我们再次翻出上面那张图

假定我们要求1-5的和，我们从根开始看，根被分成了两个区间，分别是1-4,5-8.不难发现1-4这个区间是完全在我们需要查询的1-5之间的，所以，我们直接返回1-4的sum，再看5-8，再被分成5-6与7-8,5-6与要查询的1-5有交集，所以继续查询5-6，此时被分成5and6，5完全在1-5之内，所以返回5的sum.

有人可能会说了，这个我用脚指头都能算出来，为啥还要这么麻烦？好像确实是这样

但你想过如果100w个数需要查询99w个的和呢?此时，线段树又简洁，还比朴素的累计时间复杂度要低很多，所以自然是我们的不二之选。

下面的第一个代码就是所说的查询功能

int chazhao(int x,int l,int r)
{
    if(node[x].l>=l && node[x].r<=r)
    return node[x].sum;
   //如果完全包括
    if(node[x].r<l || node[x].l>r)
    return 0;
    //如果完全没有交集
    int ans=0;
    if(node[x*2].r>=l)
    ans+=chazhao(x*2,l,r);
    //如果这个区间的左儿子和目标区间又交集，就搜索左儿子
    if(node[x*2+1].l<=r)                        ans+=chazhao(x*2+1,l,r);
   //如果这个区间的右儿子和目标区间又交集，就搜索右儿子
    return ans;
}

我身边的OIer都直接在无脑背这个，但我还是觉得理解记忆比较好 不然如果在考场上忘了，或者脑抽了

咳咳咳,回归正题.

那么如何实现修改单点呢?

其实也不难

还记得我们最初推出来的定理么node[i].sum=node[i2].sum+node[i2+1].sum

我再使用一次那张图 假定我们需要修改的是原图的五号点，其中黄色是去的路径，红色是返回的路径，回来时候红色的+标记就是把这个点加上这个值。

如果你还是不懂确实很难，那么听我通俗来说

相当于我们在5号加上了k,然后因为需要满足node[x].sum=node[(x<<1)|1].sum+node[(x<<1)].sum; 所以往上依照这个更新就行了，直接上代码

void add(int i,int y,int x)
{
    if(node[i].l==node[i].r)
    {//如果区间只有1个点，那就找到了
        node[i].sum+=x;
        return ;
    }
    if(y<=node[i*2].r)
    add(i*2,y,x);
   else  add(i*2+1,y,x); //向在的方向搜
   tree[i].sum=node[i*2].sum+node[i*2+1].sum;
   //维护一下下定理 
   return ;
}

线段树初级教学 完毕! 如果你认认真真学完了，而且都会了，你就得到了不错的入门

我准备出个二继续深入讲线段树，码字绘图都不易，点个赞走行不行

如有错误，请联系我订正