70分求调

#include<bits/stdc++.h>
using namespace std;
#define mx 400005
int num[mx],tree[mx],lz[mx*4],n,m;
void build(int root,int start,int end)
{
    lz[root] = 0;
    if(start == end)
    {
        tree[root] = num[start];
        return;
    }
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start+end)/2;
    build(leftroot,start,mid);
    build(rightroot,mid+1,end);
    tree[root] = tree[leftroot]+tree[rightroot];
}
void push_down(int l,int r,int root)
{
    lz[root<<1]+=lz[root],lz[root<<1|1]+=lz[root];
    int mid = (l+r)>>1;
    tree[root<<1]+=(mid-l+1)*lz[root],tree[root<<1|1]+=(r-mid)*lz[root];
    lz[root] = 0;
}
long long query(int root,int start,int end,int l,int r)
{
    if(l <= start && r >= end)
        return tree[root];
    push_down(root,start,end);
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start+end)/2;
    long long sum = 0;
    if(l <= mid)
        sum += query(leftroot,start,mid,l,r);
    if(r > mid)
        sum += query(rightroot,mid+1,end,l,r);
    return sum;
}
void update(int root,int start,int end,int l,int r,int k){
    if(start == end)
    {
        tree[root] += k;
        lz[root] += k;
        return;
    }
    push_down(start,end,root);
    int leftroot = root * 2;
    int rightroot = root * 2 + 1;
    int mid = (start+end)/2;
    if(l <= mid)
        update(leftroot,start,mid,l,r,k);
    if(r > mid)
        update(rightroot,mid+1,end,l,r,k);
    tree[root] = tree[leftroot] + tree[rightroot];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++) scanf("%d",num+i);
    build(1,1,n+1);
    for(int i = 0;i < m;i++)
    {
        int c,l,r;
        scanf("%d%d%d",&c,&l,&r);
        if(c == 1)
        {
            int k;
            scanf("%d",&k);
            update(1,1,n+1,l,r,k);
        }
        if(c == 2)
        {
            cout<<query(1,1,n+1,l,r)<<endl;
        }
    }
    return 0;
}