题目描述

我看这题好像没有用c语言写的就自己写一个，其实线段
树你理解了就好写了，不要因为他太长就害怕。希望这个
可以给你一些帮助

C 代码

#include <stdio.h>
#define ls(d) d<<1 //左孩子相当于d*2
#define rs(d) d<<1|1 //右孩子相当于d*2+1
#define N 100010
int dav[N<<2];
int lan[N<<2];
int n,m,k,a,b;

void he(int d)
{
    dav[d]=dav[ls(d)]+dav[rs(d)]; //左孩子加右孩子就等于这个区间的和
}

void create(int d,int l,int r)
{
    int mid=l+r>>1; //这个相当于(l+r)/2,不加括号应为>>优先级比+小（绝对不是应为我懒）
    lan[d]=0;
    if(l==r) {
        scanf("%d",&dav[d]);
        return ;
    }
    create(ls(d),l,mid);
    create(rs(d),mid+1,r);
    he(d);
}

void f(int d,int l,int r,int y)
{
    dav[d]+=y;
    lan[d]+=y;
}

void ya(int d,int l,int r) //向下压，应为你加的数是给的这个区间的根，根下面的还没改所以要
{                           //将这个数值给他的左右孩子，这个叫懒标记你们可以去网上看看
    int mid=l+r>>1;     
    f(ls(d),l,mid,lan[d]);
    f(rs(d),mid+1,r,lan[d]);
    lan[d]=0;
}

void gen(int d,int l,int r,int x,int y)
{
    int mid=l+r>>1;
    if(x<=l && r<=x )
    {
        dav[d]+=y;  
        lan[d]+=y;  //懒标记
        return ;
    }
    if(lan[d]!=0)   //这个可以没有看你心情
        ya(d,l,r);
    if(x<=mid) gen(ls(d),l,mid,x,y);    //这个其实是二分
    else gen(rs(d),mid+1,r,x,y);
    he(d);
}

int cha(int x,int y,int d,int l,int r)
{
    int mid=l+r>>1;
    int res=0;
    if(x<=l&&r<=y) return dav[d];
    if(lan[d]!=0)   //这个可以没有
        ya(d,l,r);  //应为懒标记的特性这里要加上这个以防给的数值没有向下压
    if(x<=mid) res+=cha(x,y,ls(d),l,mid);
    if(y>mid) res+=cha(x,y,rs(d),mid+1,r);
    return res;
}

int main()
{
    scanf("%d%d",&n,&m);
    create(1,1,n);
    while(m--){
       scanf("%d%d%d",&k,&a,&b);
       if(k==0) {
           printf("%d\n",cha(a,b,1,1,n));
       } else {
           gen(1,1,n,a,b);
       }
    }
    return 0;
}
//可ac