线段树板子C++

    struct node
    {
        int l,r,sum,lazy;
        node *lson,*rson;
        node()
        {
            l = r = sum = lazy = 0;
            lson = rson = NULL;
        }
    };

    void update(node *k)
    {
        k->sum = 0;
        if(k->lson)
            k->sum += k->lson->sum;
        if(k->rson)
            k->sum += k->rson->sum;
    }

    //同范围加上一个相同的数
    void changeSegment(node *k,int l,int r,int x)
    {
        if(k->l==l && k->r==r)
        {
            k->sum += (r-l+1)*x;
            k->lazy += x;
            return;
        }

        int mid = (k->l+k->r)/2;
        if(r <= mid)
        {
            if(!k->lson)
            {
                k->lson = new node;
                k->lson->l = k->l;
                k->lson->r = mid;
            }

            changeSegment(k->lson,l,r);
        }
        else if(l > mid)
        {
            if(!k->rson)
            {
                k->rson = new node;
                k->rson->l = mid+1;
                k->rson->r = k->r;
            }

            changeSegment(k->rson,l,r);
        }

        update(k);
    }

    void changePoint(node *k,int x,int target)
    {
        if(k->l == k->r)
        {
            k->sum = target;
            return;
        }

        int mid = (k->l+k->r)/2;
        if(x <= mid)
        {
            if(!k->lson)
            {
                k->lson = new node;
                k->lson->l = k->l;
                k->lson->r = mid;
            }

            changePoint(k->lson,x,target);
        }
        else
        {
            if(!k->rson)
            {
                k->rson = new node;
                k->rson->l = mid+1;
                k->rson->r = k->r;
            }

            changePoint(k->rson,x,target);
        }

        update(k);
    }

    void pushdown(node *k)
    {
        if(k->l == k->r)
        {
            k->lazy = 0;
            return ;
        }

        if(k->lson)
        {
            k->lson->sum += (k->lson->r-k->lson->l+1)*k->lazy;
            k->lson->lazy += k->lazy;
        }
        if(k->rson)
        {
            k->rson->sum += (k->rson->r-k->rson->l+1)*k->lazy;
            k->rson->lazy += k->lazy;
        }

        k->lazy = 0;
    }

    int query(node *k,int l,int r)
    {
        if(k->lazy)
            pushdown(k);
            
        if(k->l==l && k->r==r)
            return k->sum;
        
        int mid = (k->l+k->r)/2;

        if(r <= mid)
            return query(k->lson,l,r);
        else if(l > mid)
            return query(k->rson,l,r);
        else
            return query(k->lson,l,mid)+query(k->rson,mid+1,r);
    }

    node *root = new node;