学步园

今天看了ZWK在清华的有关线段树的课件----统计的力量，顿时感觉神犇就是不一样，难得的国家集训队队员，能够自己创造属于自己的算法。。。

第一种也是最简单的线段树：  单点更新型。

在以后的题目中会依次介绍各种类型的线段树。。。

       什么是线段树呢?线段树其实就是和我们平时所说的二叉搜索树，是一种区间树，它会将一个区间划分成一些单元小区间，每个单元小区间在我们的定义下，就会严格成为一个点，可就是叶子节点。（ 看不懂没关系，继续往下看 ）

   线段树大体看上去，和一个二叉树很像，其实，他就是一种特殊的二叉树，当然如果是一棵树，我们自然少不了对于树的 建立，查找，删除和增加等基本的操作。

          对于一个非叶子结点来说，如果用[ l , r ] 来表示这个结点的话，我们就可以利用[ l, (l+r)>>1 ]来表示左儿子，用[ (r+l)>>1|1,r ]来表示右儿子。所以说，线段树是一个平衡二叉树。使用线段树可以快速查找某一个结点在若干条线段中出现的次数，时间复杂度为O（logN），N为为儿子节点的数目，也就是整个区间的长度，这就对应了上面线段树的概念。

（1） 建树过程，实际上线段树的建立和其他树一样，也是一个递归的过程，通过递归来建立一棵树，是很多基础哪怕是高级数据结构都管用的手法和技巧。。

首先定义一个结构体类型，来存放线段树中的每个结点。

struct node
{
    int left, right;
    int sum;
}b[maxn>>2];

maxn表示区间的长度，究竟为什么要开至少是长度四倍的数组，后面会讲到。。

然后，我们快乐的递归建树吧~

void build ( int left,int right, int i )
{
    b[i].left = left;
    b[i].right = right;
    if ( left == right )
    {
        b[i].sum = a[left];
        return;
    } 
    int mid = (left+right)>>1;
    build(left,mid,i<<1);
    build(mid+1,right,i<<1|1);
}

相信这个函数大家看起来都该没啥问题吧，，很简单的递归调用，然后注意递归终止的条件。

树建好了，下来就是我们要查找那些我们需要的结点了，

int Query( int left,int right,int i )
{
    if ( b[i].left == left && b[i].right == right )
        return b[i].sum;
    int mid = ( b[i].left+b[i].right)>>1;
    if ( right<=mid )
        return Query(left,right,i<<1);
    else if ( left>mid )
        return Query(left,right,i<<1|1);
    else
        return Query(left,mid,i<<1)+Query(mid+1,right,i<<1|1);
    
}

3种情况，分别去考虑下，其实代码也不难，认真读读，然后在手模下。

再下来我们介绍增加和删除的功能。。。。

void Add( int id,int num,int i )
{
    if ( b[i].left == b[i].right )
    {
        b[i].sum+=num;
        return;
    }
    else
    {
        b[i].sum+=num;
        if ( id<=b[i*2].right )
            Add(id,num,i<<1);
        else
            Add(id,num,i<<1|1);
    }
}

哦了，

三个函数的都写好了，那么，我们下来就来完成这道题吧!

代码下次更新~