1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 const int maxn = 100000 + 500; 6 struct data { 7     int l; 8     int r; 9     long long sum;10     long long lazy;11 };12 13 int a[maxn];14 data p[maxn * 3];15 int n, m;16 int oop, x, y, z;17 18 void update(int x) {19     p[x].sum += p[x].lazy * (p[x].r - p[x].l + 1);20     if (p[x].r == p[x].l) {21         p[x].lazy = 0;22         return;23     }24     p[2 * x].lazy += p[x].lazy;25     p[2 * x + 1].lazy += p[x].lazy;26     p[x].lazy = 0;27 }28 29 void build(int x, int l, int r) {30     p[x].l = l;31     p[x].r = r;32     if (l == r) {33         p[x].sum = a[l];34         return;        35     }36     int mid = (l + r) >> 1;37     build(2 * x, l, mid);38     build(2 * x + 1, mid + 1, r);39     p[x].sum = p[2 * x].sum + p[2 * x + 1].sum;40 }41 42 void change(int x, int l, int r, int z) {43     if (p[x].l == l && p[x].r == r) {44         p[x].lazy += z;45         return;46     }47     if (p[x].lazy) update(x);48     int mid = (p[x].l + p[x].r) >> 1;49     if (r <= mid) change(2 * x, l, r, z);50     else if (l > mid) change(2 * x + 1, l, r, z);51     else {52         change(2 * x, l, mid, z);53         change(2 * x + 1, mid + 1, r, z);54     }55     p[x].sum = p[2 * x].sum + p[2 * x + 1].sum + 56                 p[2 * x].lazy * (p[2 * x].r - p[2 * x].l + 1) + 57                 p[2 * x + 1].lazy * (p[2 * x + 1].r - p[2 * x + 1].l + 1);58 59 }60 61 long long xfind(int x, int l, int r) {62     if (p[x].lazy) update(x);63     if (p[x].l == l && p[x].r == r) {64         return p[x].sum;65     }66     int mid = (p[x].l + p[x].r) >> 1;67     if (r <= mid) return (xfind(2 * x, l, r));68     else if (l > mid) return (xfind(2 * x + 1, l, r));69     else return (xfind(2 * x, l, mid) + xfind(2 * x + 1, mid + 1, r));70 }71 72 73 int main () {74     scanf("%d %d", &n, &m);75     for (int i = 1; i <= n; i++) scanf("%d", &a[i]);76     build(1, 1, n);77     for (int i = 1; i <= m; i++) {78         scanf("%d %d %d", &oop, &x, &y);79         if (oop == 1) {80             scanf("%d", &z);81             change(1, x, y, z);82         } else {83             printf("%lld\n", xfind(1, x, y));84         }85     }86 87     return 0;88 }