lazy propagation

#include <iostream>

#include <cstdio>

#include <algorithm>

#include <climits>

#include <vector>

#include <queue>

#include <cstring>

#include <stack>

#include <string>

#include <set>

#include <map>

#include <math.h>

#define INF 1000000000

using namespace std;

vector<long long > tree;

vector<long long > a;

vector<long long> lazy;

int n, m, k;

long long init(int node,long long x,long long y)

{

    if (x == y)

        return tree[node] = a[x];

    return tree[node] = init(node * 2, x, (x + y) / 2) + init(node * 2 + 1, (x + y) / 2 + 1, y);

}

void update_lazy(int node, long long x, long long y)

{

    if (lazy[node] != 0)

    {

        tree[node] += (y - x + 1)*lazy[node];

        if (x != y)

        {

            lazy[node * 2] += lazy[node];

            lazy[node * 2 + 1] += lazy[node];

        }

        lazy[node] = 0;

    }

}

long long query(int low, int high, int node, long long x, long long y)

{

    update_lazy(node, x, y);

    if (y < low || high < x)

        return 0;

    if (low <= x&&y <= high)

        return tree[node];

    long long mid = (x + y) / 2;

    

    return query(low, high, node * 2, x, mid) + query(low, high, node * 2 + 1, mid + 1, y);

}

void update(int low, int high,long long val,int node, long long x, long long y)

{

    update_lazy(node, x, y);

    if (y < low || high < x)

        return;

    if (low <= x&&y <= high)

    {

        tree[node] += (y - x + 1)*val;

        if (x != y)

        {

            lazy[node * 2] += val;

            lazy[node * 2 + 1] += val;

        }

        return;

    }

    long long mid = (x + y) / 2;

    update(low, high, val, node * 2, x, mid);

    update(low, high, val, node * 2 + 1, mid + 1, y);

    tree[node] = tree[node * 2] + tree[node * 2 + 1];

}

int main()

{

    scanf("%d%d%d", &n, &m, &k);

    int tmp;

    a.resize(2*n);

    tree.resize(5*n);

    lazy.resize(5*n);

    

    

    

    for (int i = 1; i <= n; i++)

    {

        scanf("%lld", &a[i]);

    }

    

    init(1, 1, n);

    

    m+=k;

    while(m--){

        scanf("%d", &tmp);

        if (tmp == 1)

        {

            int a, b;

            long long c;

            scanf("%d%d%lld", &a, &b, &c);

            update(a, b , c, 1, 1, n );

        }

        else if (tmp == 2)

        {

            int a, b;

            scanf("%d%d", &a, &b);

            printf("%lld\n", query(a, b , 1, 1, n));

        }

    }

    return 0;

}