using namespace std;

struct Bitree{
	long long bi[1000010],ibi[1000010];
	long long n;
	long long lowbit(long long x){
		return (x & -x);
	}
	void init(long long size){
		n = size;
		for(long long i = 0; i <= n; i++){
			bi[i] = 0;
			ibi[i]=0;
		}
	}
	void add(long long pos,long long val){
		long long vb=val;
		long long vib=val*pos;
		while(pos <= n){
			bi[pos] += vb;
			ibi[pos] += vib;
			pos += lowbit(pos);
		}
	}
	long long queryb(long long pos){
		long long ans = 0;
		while(pos > 0){
			ans += bi[pos];
			pos -= lowbit(pos);
		}
		return ans;
	}
	long long queryib(long long pos){
		long long ans = 0;
		while(pos > 0){
			ans += ibi[pos];
			pos -= lowbit(pos);
		}
		return ans;
	}
	long long query(long long pos){
		return queryb(pos) *(pos+1) -queryib(pos);
	}
	long long query(long long l,long long r){
		return query(r)-query(l-1);
	}
};
Bitree bitree;
long long a[1000005];
int main(){ 
	long long n,m;
	cin>>n>>m;
	bitree.init(n);
	for(long long i=1;i<=n;i++){
		cin>>a[i];
		bitree.add(i,a[i]-a[i-1]);
	}
	for(long long i=1;i<=m;i++){
		long long op;
		cin>>op;
		if(op==1){
			long long l,r,v;
			cin>>l>>r>>v;
			bitree.add(l,v);
			bitree.add(r+1,-v);
		}
		if(op==2){
			long long l,r;
			cin>>l>>r;
			cout<<bitree.query(l,r)<<'\n';
		}
	}
	return 0; 
}

```
`

using namespace std;
struct Bitree{
	int tree[500050],n;
	int lowbits(int x){
		return x&-x;
	}
	void init(int size){
		n=size;
		for(int i=0;i<=n;i++) tree[i]=0;
	}
	void add(int pos,int val){
		while(pos<=n){
			tree[pos]+=val;
			pos+=lowbits(pos);
		}
	}
	int query(int pos){
		int ans=0;
		while(pos>0){
			ans+=tree[pos];
			pos-=lowbits(pos);
		}
		return ans;
	}
	int query(int l,int r){
		return query(r) - query(l - 1);
	}
	
};
Bitree  bitree;
int main(){
	int n,m;
	
	cin>>n>>m;
	bitree.init(n);
	for(int i=1;i<=n;i++){
		int val;
		cin>>val;
		bitree.add(i,val);
	}
	for(int i=1;i<=m;i++){
		int op,x,y;
		cin>>op>>x>>y;
		if(op==1){
			bitree.add(x,y);
		}else{
			cout<<bitree.query(x,y)<<'\n';
			
		}
	}
	return 0;
}`