树状数组和线段树

树状数组:
1.将某一个数加上k
2.求出某区间每一个数的和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[500000+10];
ll lowbit(ll x){return x&(-x);}
void add(ll x,ll k){
	while(x<=n){
		a[x]+=k;
		x+=lowbit(x);
	}
}
ll query(ll x){
	ll ret=0;
	while(x>0){
		ret+=a[x];
		x-=lowbit(x);
	}
	return ret;
}
int main(){
	cin >> n >> m;
	for(ll i=1;i<=n;i++){
		ll temp;
		cin >> temp;
		a[i]+=temp;
		if(i+lowbit(i)<=n)a[i+lowbit(i)]+=a[i];
	}
	for(ll i=1;i<=m;i++){
		ll op,x,y;
		cin >> op >> x >> y;
		if(op==1)add(x,y);
		else cout << query(y)-query(x-1) << endl;
	}
	return 0;
}

树状数组:
1.将某区间每一个数加上k
2.求出某一个数的值

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[500000+10],b[500000+10];
ll lowbit(ll x){return x&(-x);}
void add(ll x,ll k){
	while(x<=n){
		a[x]+=k;
		x+=lowbit(x);
	}
}
ll query(ll x){
	ll ret=0;
	while(x>0){
		ret+=a[x];
		x-=lowbit(x);
	}
	return ret;
}
int main(){
	cin >> n >> m;
	for(ll i=1;i<=n;i++)cin >> b[i];
	for(ll i=1;i<=m;i++){
		ll op,x,y,k;
		cin >> op >> x;
		if(op==1){
			cin >> y >> k;
			add(x,k);
			add(y+1,-k);
		}else{
			cout << query(x)+b[x] << endl;
		}
	}
	return 0;
}

树状数组:
1.将某区间每一个数加上k
2.求出某区间每一个数的和

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[2][500000+10],b[500000+10];
ll lowbit(ll x){
	return x&(-x);
}
void add(ll type,ll x,ll k){
	while(x<=n){
		a[type][x]+=k;
		x+=lowbit(x);
	}
}
ll query(ll type,ll x){
	ll ret=0;
	while(x>0){
		ret+=a[type][x];
		x-=lowbit(x);
	}
	return ret;
}
int main(){
	cin >> n >> m;
	for(ll i=1;i<=n;i++)cin >> b[i],b[i]+=b[i-1];
	for(ll i=1;i<=m;i++){
		ll op,x,y,k,ans;
		cin >> op >> x >> y;
		if(op==1){
			cin >> k;
			add(0,x,k);
			add(0,y+1,-k);
			add(1,x,k*x);
			add(1,y+1,-k*(y+1));
		}else{
			ans=(y+1)*query(0,y)-query(1,y)-x*query(0,x-1)+query(1,x-1)+b[y]-b[x-1];
			cout << ans << endl;
		}
	}
	return 0;
}