SegmentTree (IncrementalUpdate)

#include <cstdio>
#include <cstring>

class SegmentTree
{
    int *sumTree, *prop, N, *arr;

    void prepareTree(int parent,int b,int e)
    {
        int mid=(b+e)>>1, left=(parent<<1)+1, right=left+1;

        if(b!=e) prepareTree(left,b,mid), prepareTree(right,mid+1,e), sumTree[parent]=sumTree[left]+sumTree[right];
        else sumTree[parent]=arr[b];
    }

    int sumQuery(int parent, int b,int e, int &l,int &r, int carry=0)
    {
        if(b>r || e<l) return 0;
        if(b>=l && e<=r) return sumTree[parent] + carry*(e-b+1);

        carry+=prop[parent];
        int mid=(b+e)>>1, left=(parent<<1)+1, right=left+1;

        return sumQuery(left, b,mid, l,r, carry) + sumQuery(right, mid+1,e, l,r, carry);
    }

    void update(int parent, int b,int e, int &l,int &r, int dx)
    {
        if(b>r || e<l) return;
        if(b>=l && e<=r)
        {
            sumTree[parent]+=(e-b+1)*dx;
            prop[parent]+=dx;
            return;
        }

        int mid=(b+e)>>1, left=(parent<<1)+1, right=left+1;

        update(left, b,mid, l,r, dx), update(right, mid+1,e, l,r, dx);

        sumTree[parent]= sumTree[left]+sumTree[right] + prop[parent]*(e-b+1);
    }

public:
    SegmentTree(int arr_[],int N_)
    {
        N=N_;
        sumTree=new int[4*N+3];
        prop=new int[4*N+3];
        for(int i=0;i<=4*N;i++) prop[i]=0;

        arr=arr_;
        prepareTree(0,0,N-1);
        arr=NULL;
    }

    int getSum(int l,int r)
    {
        return sumQuery(0, 0,N-1, l,r);
    }

    void update(int l,int r, int dx)    //increments the indices between l and r (inclusive) by dx
    {
        update(0, 0,N-1, l,r, dx);
    }
};

int main()
{
    /* code */
    return 0;
}