线段树

题意：

分析：

以前没学线段树时，看一些题解总是会有这句话“这题可以用线段树做，当然不必这么麻烦。。。。。”
总会产生兴趣，线段树是什么呀。上了雨神的课终于是清楚了。
能够解决复杂问题的线段树也是起于简单的想法的呢。

不说了看着一题，很明显是区间求和问题。那么重点便为我们的lazy标记了！
我们lazy标记应该为什么呢？标记这个区间最左端的元素值！而这个区间一定要应该从头到尾都是等差的
即a1,a1+1,a1+2,a1+3......我们这样规定。
这样就可以了。。。。。。

#include<iostream>
#include<algorithm>
using namespace std;
#define lson now<<1
#define rson now<<1|1
typedef long long ll;
const int max_n = 1e5 + 100;
int n, m;
struct node
{
    int l, r, lazy;ll w;
}tree[max_n << 2];

void build(int l,int r,int now) {
    tree[now].l = l;tree[now].r = r;tree[now].lazy = 0;
    if (l == r) {
        cin >> tree[now].w;
        return;
    }
    int mid = (tree[now].l + tree[now].r) >> 1;
    build(l, mid, lson);
    build(mid + 1, r, rson);
    tree[now].w = tree[lson].w + tree[rson].w;
}

void pushdown(int now) {
    if (tree[now].lazy) {
        tree[lson].lazy = tree[now].lazy;
        tree[rson].lazy = tree[now].lazy + tree[lson].r - tree[lson].l + 1;
        tree[lson].w = (tree[lson].r - tree[lson].l + 1) * (2 * tree[lson].lazy + tree[lson].r - tree[lson].l) >> 1;
        tree[rson].w = (tree[rson].r - tree[rson].l + 1) * (2 * tree[rson].lazy + tree[rson].r - tree[rson].l) >> 1;
        tree[now].lazy = 0;
    }
}

void renew(int x,int y,int k,int now) {
    if (tree[now].l >= x && tree[now].r <= y) {
        tree[now].lazy = tree[now].l - x + k;
        tree[now].w = (tree[now].r - tree[now].l + 1) * (2 * tree[now].lazy + tree[now].r - tree[now].l) >> 1;
        return;
    }
    if (tree[now].lazy)pushdown(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    if (mid >= x)renew(x, y, k, lson);
    if (mid < y)renew(x, y, k, rson);
    tree[now].w = tree[lson].w + tree[rson].w;
}

ll quiry(int x, int y,int now) {
    if (tree[now].l >= x && tree[now].r <= y)return tree[now].w;
    if (tree[now].lazy)pushdown(now);
    int mid = (tree[now].l + tree[now].r) >> 1;
    ll ans = 0;
    if (mid >= x)ans += quiry(x, y, lson);
    if (mid < y)ans += quiry(x, y, rson);
    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;build(1, n, 1);
    while (m--) {
        int type;cin >> type;
        if (type == 1) {
            int l, r, k;
            cin >> l >> r >> k;
            renew(l, r, k, 1);
        }
        else {
            int l, r;cin >> l >> r;
            cout << quiry(l, r, 1) << endl;
        }
    }
}