树状数组:
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;
}