线段树

线段树札记

线段树不是区间树，线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。注意他是把一段连续的区间分为单元区间为叶子节点的一颗数，以此为基础，展开一系列牛逼的计算。

首先就是如何建立这么一个线段树？

如此递归地建立，对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，右儿子表示的区间为[(a+b)/2+1,b]。就可以建立一张如下图的线段树：

伪代码：

  construct(index,left,right) {

 tree[index].left = left;

 tree[index].right = right;

 if left=right

   return;

 mid = (left+right)/2

construct(2*index,left,mid)

construct(2*index+1,mid+1,right)

}

　　如此一个线段树就创建好了，父亲节点与孩子节点是index->(2*index,2*index+1),用此来创建一颗二叉树，所以在结构体里面只需要两个字段一个是left，一个是right

创建好线段树之后，一个重要操作就是插入操作，这个是奠定后面各种牛逼操作的基础。那么如何插入一段区间呢？(假设区间为[begin,end])

 insert(index,begin,end)

if begin=tree[index].left&&end=tree[index].right=end  //注意这里是等于号

  tree[index].cover++

int mid = (tree[index].left+tree[index].right)/2

if mid >=end

  insert(2*index,begin,end)

else

  insert(2*index+1,begin,end)

end

end

这里为cover添加了一个字段cover，计算这段区间的区间

这个cover是后面用来查询用的

到目前为止，该用的数据结构已经维护好了。现在开始用了，查询一个点在区间中出现的次数。从根节点开始到[x,x]叶子的这条路径中所有点计数相加方为x出现次数

查询x在区间中出现的次数。

query(index,x)

 mid = (tree[index].left + tree[index].right)/2

 if x<=mid

  return query(2*index,x)+tree[index].cover

else

  return query(2*index+1,x)+tree[index].cover

end

题目练习　

1,单点更新

HDU 敌兵布阵

题目很简单就是一道赤裸裸的线段树的题目。不过好久没敲代码了，生疏了，还是被一些小问题搞得很烦，可能自己内心也是太烦了。

最坑爹的是strcmp(str,"End")和str=="End"字符串的比较吧

占位符。。。。。。。。。。。。。

对于一个单节点更新的时候可以从上往下寻找的时候就更新节点的cover域，也可以在回朔的时候更新节点的cover域；

    if(x>=tree[index].left&&x<=tree[index].right) // >=  -> == 
     {
         tree[index].cover += value;
         if(tree[index].left==x&&tree[index].right==x)
             return;
     }

也可以在

  int mid=(tree[index].left+tree[index].right)/2;
     if(mid>=x) //sometime i forget to consider the equal condition,but it's important; 
        update(2*index,x,value);
     else
        update(2*index+1,x,value); 
     //tree[index].cover += value; 对于单节点更新，是在查找的时候更新父亲节点，还是回朔时候更新父亲节点都是可行的

代码：

#include<stdio.h>
#include<string.h>

#define MAX 50010

struct Node
{
       int left;
       int right;
       int cover;
};
Node * tree= new Node[MAX*4];

int data[MAX];

void build(int index,int left,int right)
{
     tree[index].left = left;
     tree[index].right= right;
     //printf("%d %d %d
",index,left,right);
     if(left==right)
     {
        tree[index].cover = data[left];
        // printf("%d %d %d %d
",index,left,right,tree[index].cover);
        return;
     }
     int mid = (left+right)/2;
     build(2*index,left,mid);
     build(2*index+1,mid+1,right);
     tree[index].cover = tree[2*index].cover + tree[2*index+1].cover; //update parent's cover field,not just update leaf node   
}

void update(int index,int x,int value)
{
     
     //printf("%d %d %d
",index,tree[index].left,tree[index].right);
     if(x>=tree[index].left&&x<=tree[index].right) // >=  -> == 
     {
         tree[index].cover += value;
         if(tree[index].left==x&&tree[index].right==x)
             return;
     }

     int mid=(tree[index].left+tree[index].right)/2;
     if(mid>=x) //sometime i forget to consider the equal condition,but it's important; 
        update(2*index,x,value);
     else
        update(2*index+1,x,value); 
     //tree[index].cover += value; 对于单节点更新，是在查找的时候更新父亲节点，还是回朔时候更新父亲节点都是可行的 
}

int query(int index,int left,int right)
{
    //printf("%d %d %d
",index,left,right);
    //getchar();
    if(left==tree[index].left&&right==tree[index].right)
    {
       return tree[index].cover;
    }
    int mid=(tree[index].left+tree[index].right)/2;
    if(mid>=right)
       return query(2*index,left,right);
    else if(mid<left)
       return query(2*index+1,left,right);
    else
       return query(2*index,left,mid)+query(2*index+1,mid+1,right);
}

int main()
{
    int T,N;
    char  str[20];
    scanf("%d",&T);
    int p,v;
    for(int s = 1; s <= T;s++)
    {
       //printf("%d",MAX*4);
       memset(tree,0,sizeof(Node)*MAX*4);
       memset(data,0,sizeof(int)*MAX);
       scanf("%d",&N);
       for(int i = 1; i<=N;i++)
       {
        scanf("%d",&data[i]);
       }
       build(1,1,N);
     //  for(int i = 1;i<=4*N;i++)
    //   {
    //      printf("%d ",tree[i].cover);
   //    }
       printf("Case %d:
",s);
       while(true) //while(scanf("%s",str)&&str!="End") str为End时候不起作用 
       {
           scanf("%s",str);
          // printf("%s",str);
           if(strcmp(str,"End")==0)
              break;
           scanf("%d%d",&p,&v);
           if(strcmp(str,"Add")==0)
           {
             update(1,p,v);                       
           }else if(strcmp(str,"Sub")==0){
             update(1,p,-v);
           }
           else if(strcmp(str,"Query")==0)
           {
             printf("%d
",query(1,p,v));
           }
       }  
      // printf("end %d",s);
    }
    return 0;
}