void pushup(int o){tree[o]=tree[o<<1]+tree[o<<1|1];}
void build(int o,int L,int R)
{
    if(L==R){
        tree[o]=arr[L];//也可以写成： scanf("%d",&tree[o]); 
        return ;
    }
    int M = (L+R)>>1;
    build(int o<<1,L,M);
    build(int o<<1|1,M+1,R);
    pushup(o);
}

void update(int o,int L,int R,int x,int val)
{
    if(L==R){//找到了要修改的值 
        tree[o]+=val;
        return ;
    }
    int M = (L+R)<<1;
    if(x>M) update(o<<1|1,M+1,R,x,val);//如果要修改的点在左右端点的右边的话，那就是要更新左端点的值，并且当前标号o也要做相应的变换 
    else update(o<<1,L,M,x,val);
    pushup(o);//因为叶子节点的值有更新，所以祖先节点还是有改变。 
}

int query(int o,int L,int R,int ql,int qr)
{
    if(ql>=L&&R>=qr) return tree[o];//找到叶子节点，把叶子节点的值加入所求的ret中。 
    int M = (L+R)>>1;
    int ret = 0 ;
    if(ql >= M) ret += query(o<<1,L,M,ql,qr);//往左边找 
    if(ql < M) ret += query(o<<1|1,M+1,R,ql,qr);//往右 
    return ret ;//返回和  
}

void pushdown(int o,int L,int R)
{
    if(L==R) {
        tree[o] += lazy[o];//到达叶子节点，没法分配任务就把总值更新了 
        return ;
    }
    lazy[o<<1] += lazy[o];//把任务分配给自己的左右儿子 
    lazy[o<<1|1] += lazy[o];
    lazy[o] = 0 ;//任务分配完自己清零 
}
void update(int o,int L,int R,int ql ,int qr,int val)
{
    if(L==R){
        tree[o] += val ;
        return ;
    }
    pushdown(o,L,R);// 先往下传标记 
    int M=(L+R)>>1;
    if(ql<=M) update(o<<1,L,M,ql,qr,val);//改左边 
    if(qr>M) update(o<<1|1,M+1,R,ql,qr,val);//改右边 
    return ;
}