小码匠的信息学江湖:【模板】树状数组 3 ：区间修改，区间查询

5 10
2 6 6 1 1
2 1 4
1 2 5 10
2 1 3
2 2 3
1 2 2 8
1 2 3 7
1 4 4 10
2 1 2
1 4 5 6
2 3 4

15
34
32
33
50

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
#define endl '\n';
typedef long long LL;

struct node {
    LL w, d;
};

struct FenwickTree{
    vector<LL> v;
    vector<node> c;
    int n;
    FenwickTree (int l):
            n(l), c(l + 1), v(l + 1){}

    int lowbit (int a) {
        return (-a) & a;
    }

    void read() {
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", &v[i]);
        }
    }

    void initialize_2 () {
        for (int i = 1; i <= n; ++i) {
            int x = i;
            while (x <= n) {
                c[x].w += v[i] - v[i - 1];
                c[x].d += (v[i] - v[i - 1]) * (i - 1);
                x += lowbit(x);
            }
        }
    }

    node cnt (int a) {
        node ans = {0, 0};
        for(; a > 0; a -= lowbit(a)) {
            ans.w += c[a].w;
            ans.d += c[a].d;
        }
        return ans;
    }

    void add_3(int x, LL w) {
        int i = x;
        for (; x <= n; x += lowbit(x)) {
            c[x].w += w;
            c[x].d += (i - 1) * w;
        }//区间修改+区间查询
    }

    LL ans(int l, int r) {
        return (r * cnt(r).w - cnt(r).d) - ((l - 1) * cnt(l - 1).w - cnt(l - 1).d);
        //区间修改+区间查询
    }
};

void best_coder() {
    int n, m;
    scanf ("%d%d", &n, &m);
    FenwickTree ft(n);
    ft.read();
    ft.initialize_2();
    for (int i = 0; i < m; ++i) {
        int a;
        scanf("%d", &a);
        if (a == 1) {
            int l, r;
            LL w;
            scanf("%d%d%lld", &l, &r, &w);
            ft.add_3(l, w);
            ft.add_3(r + 1, -w);
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", ft.ans(l, r));
        }
    }
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // freopen("xxx.in", "r", stdin);
    // freopen("xxx.out", "w", stdout);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // fclose(stdin);
    // fclose(stdout);

    return 0;
}