Segment Tree

int arr[1000],tree[4000];

void build(int node,int l,int r)
{
    if(l==r)
        tree[node]=arr[l];
    else{
        int mid=(l+r)/2;
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        tree[node]=tree[node*2]+tree[node*2+1];
    }
}

int sum(int node,int tl,int tr,int l,int r)
{
    if(l>r)
        return 0;
    if(l==tl && r==tr)
        return tree[node];
    int mid=(tl+tr)/2;

    return sum(node*2,tl,mid,l,min(r,mid))
        + sum(node*2+1,mid+1,tr,max(l,mid+1),r);
}

void update(int node,int l,int r,int pos,int val)
{
    if(l==r)
        tree[node]=val;
    else{
        int mid=(l+r)/2;
        if(pos<=mid)
            update(node*2,l,mid,pos,val);
        else
            update(node*2+1,mid+1,r,pos,val);
        tree[node]=tree[node*2]+tree[node*2+1];
    }
}