学步园

题目链接:  http://acm.hdu.edu.cn/showproblem.php?pid=1166

题目大意:   给出初始化的区间值，然后有三种询问

                    Query a b 询问区间[a,b]值的总和

                    Add a b 第a个元素的值加b

                    Sub a b 第a个元素的值减b

解题思路:  线段树 更新:单点增减 询问:区间和

                   每次更新在结点存储左右子树值的和，查询时就不需要查到最低，实现区间查询

                   更新时间复杂度O(logN),查询时间复杂度O(logN)

代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 100000
#define MID(a,b) (a+b)>>1
#define L(a) a<<1
#define R(a) (a<<1)+1
typedef struct snode{
    int num,left,right;
}Node;
int num[MAX];
Node Tree[MAX<<1];

void Init()
{
    memset(Tree,0,sizeof(Tree));
}

void Build(int t,int l,int r)    //以t为根结点，建立左子树为l，右子树为r的线段树
{
    int mid;
    Tree[t].left=l,Tree[t].right=r;
    if(Tree[t].left==Tree[t].right)
    {
        Tree[t].num=num[l];
        return ;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    Build(L(t),l,mid);
    Build(R(t),mid+1,r);
    Tree[t].num=Tree[L(t)].num+Tree[R(t)].num;
}

void Insert(int t,int l,int r,int n)  //向t为根结点，左子树为l，右子树为r的结点加上值n
{
    int mid;
    if(Tree[t].left==l&&Tree[t].right==r)
    {
        Tree[t].num+=n;
        return ;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    if(r<=mid)
        Insert(L(t),l,r,n);
    else if(l>=mid)
        Insert(R(t),l,r,n);
    else
    {
        Insert(L(t),l,mid,n);
        Insert(R(t),mid+1,r,n);
    }
    Tree[t].num+=n;
}

int Query(int t,int l,int r)    //查询根结点为t，左子树为l，右子树为r的结点的值
{
    int mid;
    if(Tree[t].left==l&&Tree[t].right==r)
    {
        return Tree[t].num;
    }
    mid=MID(Tree[t].left,Tree[t].right);
    if(l>mid)        //***
        return Query(R(t),l,r);
    else if(r<=mid)   //***
        return Query(L(t),l,r);
    else
    {
        int a,b;
        a=Query(L(t),l,mid);
        b=Query(R(t),mid+1,r);
        return a+b;
    }
}

int main()
{
    char ch[10];
    int t,n,i,i1,a,b;
    scanf("%d",&t);
    for(i1=1;i1<=t;i1++)
    {
        Init();         //初始化
        scanf("%d",&n);
        for(i=1;i<=n;i++)
            scanf("%d",&num[i]);
        Build(1,1,n);   //以1为根结点建立线段树
        printf("Case %d:\n",i1);
        while(scanf("%s",ch)&&strcmp(ch,"End")!=0)
        {
            scanf("%d%d",&a,&b);
            if(strcmp(ch,"Add")==0)     //第a个元素加b
                Insert(1,a,a,b);
            else if(strcmp(ch,"Sub")==0)  //第a个元素减b
                Insert(1,a,a,-b);
            else
                printf("%d\n",Query(1,a,b));  //查询[a,b]区间值的总和
        }
    }
    return 0;
}

注:原创文章，转载请注明出处