You can solve it with a lazy segment tree and maintaining two lazy values per segment. Suppose we have a query of type 1 over a segment [a, b]. Suppose now we arrived in the segment tree at some segment [c, d] that is in the range [a, b] (c >= a && d <= b). Now we should add $$$(c - a + 1) + (c - a + 2) + (c - a + 3) + ... + (d - a + 1)$$$ to the segment sum of [c, d]. This is the same as adding $$$(c - a) * (d - c + 1) + 1 + 2 + 3 + ... + (d - c + 1)$$$ to the segment sum of [c, d]. Because we make use of lazy propagation we add the values to the lazy nodes: lazy1[idx] adds $$$c - a$$$ and lazy2[idx] is increased by one (the total times you should add $$$1 + 2 + 3 + ... + (d - c + 1)$$$ to this segment so far. So you can solve it in $$$O(Q log N)$$$.

Or you could be more exotic and solve it with Fenwick Tree instead.

Here's the idea: when you add a value, say $$$x$$$, to a segment $$$[lo,\ hi]$$$, the first element is incremented by $$$x$$$, the second by $$$x + 1$$$, and so on, till the last element of the segment is incremented by $$$x + (hi - lo)$$$. Only, in this question $$$x = 1$$$. We'll see what happens to the prefix sum post an update:

Post update, in the prefix sum, the elements in the range $$$[1,\ lo)$$$ stays constant. The element in the range $$$[lo,\ hi]$$$, with an index $$$idx$$$, is incremented by $$$(idx\ -\ lo)\ *\ x\ +\ [(idx\ -\ lo)\ *\ (idx\ -\ lo\ +\ 1)]\ /\ 2$$$. And the elements in the range $$$(hi,\ N)$$$ are incremented by $$$(hi\ -\ lo\ +\ 1)\ *\ x\ +\ [(hi\ -\ lo)\ *\ (hi\ -\ lo\ +\ 1)]\ /\ 2$$$. Similar to how multiple Fenwick trees can be used to handle range updates and range queries, we can use 6 BITs here for the update. The first will take care of $$$idx$$$. The second will take care of constant terms. The third will take care of doubled $$$idx^{2}$$$. The fourth will take care of doubled $$$idx$$$. The fifth will take care of doubled constant terms. And the sixth will hold the initial prefix sum (prior to any update(s)). Notice that I've taken doubled terms because I'm splitting the terms which are being divided by $$$2$$$ so it's possible that it no longer stays divisible by $$$2$$$. Consequently, all doubled terms are halved at queries to nullify the effect. Here's the implementation, for the writing might be confusing without something concrete:

#include<bits/stdc++.h>
using namespace std;

//solution:
#define int int64_t

struct fenwick {
    int n;
    vector<int> bit[6];
    fenwick(int n) {
        this -> n = n;
        for(auto& i: bit) i.assign(n + 1, 0);
    }
    fenwick(vector<int>& a): fenwick(a.size()) {
        for(int i = 1; i <= n; ++i) updatex(i, a[i - 1], 5);
    }
    int queryx(int i, int key) {
        int result = 0;
        for(int x = i; x; x -= x & -x) result += bit[key][x];
        return result;
    }
    int query(int i) {
        int a = queryx(i, 0), b = queryx(i, 1), c = queryx(i, 2);
        int d = queryx(i, 3), e = queryx(i, 4), f = queryx(i, 5);
        return a * i + b + ((c * i * i + d * i + e) / 2) + f;
    }
    int query(int lo, int hi) {
        return query(hi) - query(lo - 1);
    }
    void updatex(int i, int delta, int key) {
        for(int x = i; x <= n; x += x & -x) bit[key][x] += delta;
    }
    void updater(int lo, int hi, int delta, int key) {
        updatex(lo, delta, key);
        updatex(hi + 1, -delta, key);
    }
    void update(int lo, int hi, int delta) {
        updater(lo, hi, delta, 0); //whole idx (mid)
        updater(lo, hi, -(lo - 1) * delta, 1); //whole constant (mid)
        updater(hi + 1, n, (hi - lo + 1) * delta, 1); //whole constant (right)
        updater(lo, hi, 1, 2); //doubled idx-squared (mid)
        updater(lo, hi, -(2 * lo - 1), 3); //doubled idx (mid)
        updater(lo, hi, lo * lo - lo, 4); //doubled constant (mid)
        updater(hi + 1, n, (hi - lo) * (hi - lo + 1), 4); //doubled constant (right)
    }
};

signed main() {
    int n, q; cin >> n >> q;
    vector<int> a(n);
    for(int& i: a) cin >> i;
    fenwick tree(a);
    while(q--) {
        int t; cin >> t;
        if(t == 1) {
            int a, b; cin >> a >> b;
            tree.update(a, b, 1);
        } else {
            int a, b; cin >> a >> b;
            cout << tree.query(a, b) << "\n";
        }
    }
    return 0;
}

There is another way to solve that problem, you can use SQRT decomposition on queries.

The main idea is, you split all $$$Q$$$ queries into $$$\sqrt{Q}$$$ blocks, each block has $$$\sqrt{Q}$$$ queries.

In each block, there are some update queries and range queries. In each block, when you read an update query, you save it into a temporary vector, and when you read a range query, you iterate through all pending queries in your temporary vector, and add to your answer, based on how that update query affect your current range (intersect, outside, or inside).

After processing each block completely, you have to update the whole array, so your array will be ready for the next blocks of query.

This solution doesn't need any advanced data structures like Fenwick Tree or Segment Tree, just an array of prefix sum is enough.

About the complexity, you may have some observation:

• In each block, the complexity to solve each block is at most $$$Q_u \times Q_r$$$, i.e the number of update queries times the number of range queries. Because of AM-GM inequality, it will not exceed $$$\dfrac{Q}{4}$$$.

• And after each block, you have to update the whole array in $$$O(N)$$$.

Then, the final complexity is $$$O((N + Q) \sqrt{Q})$$$, which is enough for the problem constraint.

You can see my code for more detail : https://hastebin.com/ogerunavit.cpp

I tried to explain my approach here.

Hope it helps.

Plus in the second part I have coded the solution, just in case anyone needs spoon-feeding :).