HDU OJ 1166 敌兵布阵 [线段树之插点问线]

题意：不用多说了……
思路：一个入门的线段树插点问线，解释在代码里
AC代码：
[cpp]
/*
线段树 -插点问线：
1：线段树中存的是对应区间的和。
2：某一点更新值时，将该点的父节点（依次向上直到根节点）都更新
3：查询时找到在线段数中分成对应的各个小区间，求sum即可。
*/
#include<stdio.h>
#include<string.h>
#define Max 4*100000
#define LL(a) a<<1;       //2*A
#define RR(a) a>>1|1;      //2*a+1
#define Mid(x,y) (x+y)>>1 //(x+y)/2
int A[Max],cnt,ans;
struct hello
{
    int l;
    int r;
    int sum;
}tree[Max];
void Build_tree(int l,int r,int t) // l,r 表示区间，t表示区间节点
{
    int x;
    tree[t].l=l;
    tree[t].r=r;
    tree[t].sum=0;
    if(l==r)
    {
       // tree[t].sum=A[l];
        while(t!=0)
        {
            tree[t].sum+=A[l];
            t/=2;
        }
        return ;
    }
    x=Mid(l,r);
    Build_tree(l,x,2*t);
    Build_tree(x+1,r,2*t+1);
}
void Updata_tree(int l,int r,int t)   // l r 表示要更新的区间，t表示当前节点
{
    if(tree[t].l==l&&tree[t].r==r)
    {
         while(t!=0)
         {
             tree[t].sum+=cnt;
             t/=2;
         }
         return ;
    }
    int x=Mid(tree[t].l,tree[t].r);
    if(x>=r)
      Updata_tree(l,r,2*t);
    else if(x+1<=l)
      Updata_tree(l,r,2*t+1);
    else
    {
        Updata_tree(l,x,2*t);
        Updata_tree(x+1,r,2*t+1);
    }
}
void Query_tree(int l,int r,int t)     // l r 表示要查询的区间 t表示当前节点
{
    //printf("inin---------------\n");
    if(tree[t].l==l&&tree[t].r==r)
    {
        //printf("outout------\n");
         ans+=tree[t].sum;
         return ;
    }
    int x=Mid(tree[t].l,tree[t].r);
    if(x>=r)
      Query_tree(l,r,2*t);
    else if(x+1<=l)
      Query_tree(l,r,2*t+1);
    else
    {
        Query_tree(l,x,2*t);
        Query_tree(x+1,r,2*t+1);
    }
}
int main()
{
    int i,j,n,m,ncase;
    scanf("%d",&ncase);
    for(n=1;n<=ncase;n++)
    {
        printf("Case %d:\n",n);
        scanf("%d",&m);
        for(i=1;i<=m;i++)
           scanf("%d",&A[i]);
        Build_tree(1,m,1);
        char str[100];
        while(scanf("%s",str)&&str[0]!='E')
        {
            int x,y;
            if(str[0]=='S')
            {
                scanf("%d%d",&x,&cnt);
                cnt=-cnt;
                Updata_tree(x,x,1);
            }
            else if(str[0]=='A')
            {
                scanf("%d%d",&x,&cnt);
                Updata_tree(x,x,1);
            }
            else if(str[0]=='Q')
            {
                scanf("%d%d",&x,&y);
                ans=0;
                Query_tree(x,y,1);
                printf("%d\n",ans);
            }
        }
    }
}

补充：软件开发 , C++ ,