---
# System prepended metadata

title: Segment Tree (1)

---

# Segment Tree (1)
dj.a408
## code
```cpp=
#include <bits/stdc++.h>
#define AC ios::sync_with_stdio(false),cin.tie(0);
#define ll long long
#define m (l+r)>>1
using namespace std;
int n,q,w,maxn=2e5+1;
vector<ll> v(maxn), seg((maxn<<2)|1), tag((maxn<<2)|1);
void push(int l, int r, int i){
	if(!tag[i]) return;
	if(r-l==1){seg[i]+=tag[i], tag[i]=0; return;}
	seg[i]+=(r-l)*tag[i];
	tag[i<<1]+=tag[i], tag[i<<1|1]+=tag[i], tag[i]=0;
}
void build(int l=0, int r=n, int i=1){
	if(r-l==1){seg[i]=v[l]; return;}
	build(l,m,i<<1), build(m,r,i<<1|1);
	seg[i]=seg[i<<1]+seg[i<<1|1];
}
ll query(int ql, int qr, int l=0, int r=n, int i=1){
	push(l,r,i);
	if(qr<=l||ql>=r) return 0;
	if(ql<=l&&qr>=r) return seg[i];
	return query(ql,qr,l,m,i<<1)+query(ql,qr,m,r,i<<1|1);
}
void modify(int ql, int qr, int val, int l=0, int r=n, int i=1){
	push(l,r,i);
	if(qr<=l||ql>=r) return;
	if(ql<=l&&qr>=r){tag[i]+=val, push(l,r,i); return;}
	modify(ql,qr,val,l,m,i<<1), modify(ql,qr,val,m,r,i<<1|1);
	seg[i]=seg[i<<1]+seg[i<<1|1];
}
int main(){ AC
	cin>>n>>q;
	for(int i=0;i<n;i++){cin>>v[i];}
	build();
	while(q--){ int x,y,k;
		cin>>w>>x>>y;
		if(w) cout<<query(x-1,y)<<'\n';
		else cin>>k, modify(x-1,y,k);
	}
}
```