# Lazy Propagation

## 1. Add Update
- [Addition to Segment](https://codeforces.com/edu/course/2/lesson/5/1/practice/contest/279634/problem/A)

## 2. Max Update
- [Applying MAX to Segment](https://codeforces.com/edu/course/2/lesson/5/1/practice/contest/279634/problem/B)

## 3. Assign Update
- [Assignment to Segment](https://codeforces.com/edu/course/2/lesson/5/1/practice/contest/279634/problem/C)

## 4. Range Query
- [Addition and Minimum](https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/A)
- [Bitwise OR and AND](https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/C)
- [Addition and Sum](https://codeforces.com/edu/course/2/lesson/5/2/practice/contest/279653/problem/D)

## 5. Maximum Segment
- [Assignment and Maximal Segment](https://codeforces.com/edu/course/2/lesson/5/3/practice/contest/280799/problem/A)

## 6. Inverse Update
- [Inverse and K-th one](https://codeforces.com/edu/course/2/lesson/5/3/practice/contest/280799/problem/B)

## 7. Classic Problems
- [Assignment, Addition, and Sum](https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/A)
- [Problem About Weighted Sum](https://codeforces.com/edu/course/2/lesson/5/4/practice/contest/280801/problem/D)

## 8. Problems
- [Lucky Queries](https://codeforces.com/contest/145/problem/E)
- [A Simple Task](https://codeforces.com/contest/558/problem/E)
- [Alphabet Permutations](https://codeforces.com/contest/610/problem/E)

## Practice Problems
- [Circular RMQ](https://codeforces.com/contest/52/problem/C)
- [DZY Loves Fibonacci Numbers](https://codeforces.com/contest/446/problem/C)
- [The Child and Sequence](https://codeforces.com/contest/438/problem/D)
- [Linear Kingdom Races](https://codeforces.com/contest/115/problem/E)
- [TorCoder](https://codeforces.com/contest/240/problem/F)
- [Lucky Array](https://codeforces.com/blog/entry/2956)
- [Kefa and Watch](https://codeforces.com/contest/580/problem/E)

## Reference Code

#include <bits/stdc++.h>

#define mid (l+r)/2

using namespace std;

typedef long long ll;

const int N = 1e5+7;

struct node {
	ll sum;
	ll lazy;
	node() {sum=lazy=0;}
};

node seg[N*4];
int n,m,a[N];

void push(int l, int r, int id) {
	if (l != r) {
		seg[id*2].lazy += seg[id].lazy;
		seg[id*2+1].lazy += seg[id].lazy;
	}
	seg[id].sum += (r-l+1)*seg[id].lazy;
	seg[id].lazy = 0;
}

node merge(node left, node right) {
	node ret;
	ret.sum = left.sum+right.sum;
	return ret;
}

void build(int l = 0, int r = n-1, int id = 1) {
	if (l == r) {
        seg[id].sum = a[l];
        seg[id].lazy = 0;
    }
    
	build(l,mid,id*2);
	build(mid+1,r,id*2+1);
	
	seg[id] = merge(seg[id*2],seg[id*2+1]);
}

void update(int L, int R, int x, int l = 0, int r = n-1, int id = 1) {
	push(l,r,id);
	
	if (l > R || r < L) return;
	if (l >= L && r <= R) {
		seg[id].lazy += x;
		push(l,r,id);
		return;
	}
	
	update(L,R,x,l,mid,id*2);
	update(L,R,x,mid+1,r,id*2+1);
	
	seg[id] = merge(seg[id*2],seg[id*2+1]);
}

node query(int L, int R, int l = 0, int r = n-1, int id = 1) {
	push(l,r,id);
	
	if (l >= L && r <= R) return seg[id];
	if (l > R || r < L) {
		node ret;
		ret.sum = 0;
		return ret;
	}
	
	return merge(query(L,R,l,mid,id*2),query(L,R,mid+1,r,id*2+1));
}

int main() {
	scanf("%d %d",&n,&m);
	for(int i = 0 ; i < n ; i++) scanf("%d",a+i);
	build();
	for(int i = 0 ; i < m ; i++) {
		int t;
		scanf("%d",&t);
		if (t == 1) {
			int l,r,v;
			scanf("%d %d %d",&l,&r,&v);
			update(l,r,v);
		} else if (t == 2) {
			int l,r;
			scanf("%d %d",&l,&r);
			r--;
			printf("%lld\n",query(l,r).sum);
		}
	}
}