线段树--单点更新-区间求和

最基础的线段树应用，以模板题:

HDU1166 敌兵布阵（线段树单点更新，区间求和

为例.

给定一个序列.

查询：查询序列$[l,r]$的和

更新：某个点的值增加x

#define mem(a,b) memset(a,b,sizeof(a))
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N=50020+20;
int sum[N<<2];
int pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
void build(int l,int r,int rt)
{
    if(l==r)
    {
        scanf("%d",&sum[rt]);
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int p,int add,int l,int r,int rt)
{
    if(l==r)
    {
        sum[rt]+=add;
        return;
    }
    int m=(l+r)>>1;
    if(p<=m) update(p,add,lson);
    else update(p,add,rson);
    pushup(rt);
}
int query(int L,int R,int l,int r,int rt)
{
    if(L<=l&&r<=R)
        return sum[rt];
    int m=(l+r)>>1;
    int ans=0;
    if(L<=m) ans+=query(L,R,lson);
    if(R>m) ans+=query(L,R,rson);
    return ans;
}
int main()
{
    int t,n,a,b,q=1;
    char s[10];
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        build(1,n,1);
        printf("Case %d:\n",q++);
        while(scanf("%s",s)&&s[0]!='E')
        {
            scanf("%d%d",&a,&b);
            if(s[0]=='Q')
                printf("%d\n",query(a,b,1,n,1));
            if(s[0]=='A')
                update(a,b,1,n,1);
            if(s[0]=='S')
                update(a,-b,1,n,1);
        }
    }
    return 0;
}

NYOJ116 士兵杀敌（二）（线段树区单点更新，区间求和,zkw线段树）

zkw线段树法:

const int N=1000000+20;  
int M,n,m,tree[N<<2];  
void pushup(int i)//向上更新  
{  
    tree[i]=tree[i<<1]+tree[i<<1|1];  
}  
void update(int x,int v)//单点修改，把x的值增加v  
{  
    for(tree[x+=M]+=v,x>>=1; x; x>>=1)  
        pushup(x);  
}  
int query(int l,int r)//求[l~r]的区间和  
{  
    int ans=0;  
    //l^r^1判断是否是兄弟节点，>0时是兄弟节点  
    //是兄弟是退出循环  
    for(l=l+M-1,r=r+M+1; l^r^1; l>>=1,r>>=1)  
    {  
        //l&1^1,r&1分别判断偶数和奇数  
        if(l&1^1) ans+=tree[l^1];//l+1  
        if(r&1)   ans+=tree[r^1];//r-1  
    }  
    return ans;  
}  
void build()  
{  
    for(M=1; M<n; M<<=1);  
    for(int i=M+1; i<=M+n; i++)  
        scanf("%d",&tree[i]);  
    for(int i=M; i>=1; i--)  
        pushup(i);  
}  
int main()  
{  
    char op[10];  
    int a,b;  
    scanf("%d%d",&n,&m);  
    build();  
    while(m--)  
    {  
        scanf("%s%d%d",op,&a,&b);  
        if(op[0]=='Q')  
            printf("%d\n",query(a,b));  
        else  
            update(a,b);  
    }  
    return 0;  
}