2025暑假训练树状数组

相关学习视频可以上bilibili看动画演示，下面是一个介绍树状数组的blog(写的非常好，配合动画演示学习起来事半功倍)

P3374 【模板】树状数组 1

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e5+5;
int n,m,flag,x,y,temp;
LL a[N];int lowbit(int t)
{return t & (-t);
}
void updata(int i,int t)
{for(;i<=n;i+=lowbit(i)) a[i]+=t;
}
LL sum(int t)
{LL res=0;for(;t;t-=lowbit(t)){res+=a[t];}return res;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>temp;updata(i,temp);}for(int i=0;i<m;i++){cin>>flag>>x>>y;if(flag==1) updata(x,y);else cout<<sum(y)-sum(x-1)<<endl;}return 0;
}

P3368 【模板】树状数组 2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
const int N=5e5+5;
ll a[N],b[N],t[N];  //b是差分数组,t是b的树状数组 
int lowbit(ll x)
{return x&(-x);
}
void updata(int x,int y,int k)
{for(;x<=n;x=x+lowbit(x))t[x]+=k;for(int j=y+1;j<=n;j=j+lowbit(j))t[j]-=k;
}
int main()
{cin>>n>>m;for(int i=1;i<=n;i++){cin>>a[i];b[i]=a[i]-a[i-1];}for(int i=1;i<=n;i++)for(int j=i;j<=n;j+=lowbit(j))t[j]+=b[i];while(m--){int flag,x,y,k;cin>>flag;if(flag==1){cin>>x>>y>>k;updata(x,y,k);}else{int ans=0;cin>>x;for(;x;x=x-lowbit(x)){ans+=t[x];}cout<<ans<<endl;}}return 0;
}

P2068 统计和

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll lst[N];
ll n,w;
ll lowbit(ll x)
{return x&(-x);
}
void updata(ll x,ll y)
{for(;x<=n;x+=lowbit(x)) lst[x]+=y;
}
ll sum(ll x)
{ll res=0;for(;x;x-=lowbit(x)) res+=lst[x];return res;
}
int main()
{cin>>n;cin>>w;char flag;ll a,b;for(ll i=1;i<=w;i++){cin>>flag>>a>>b;if(flag=='x') updata(a,b);else cout<<sum(b)-sum(a-1)<<endl;}return 0;
}

P1908 逆序对

//归并排序统计逆序对
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5+5;
ll ans=0,n,lst[N],tmp[N]; void merge(ll q[],ll l,ll r)
{if(l>=r) return;ll mid=(l+r)>>1;merge(q,l,mid);merge(q,mid+1,r);int k=0,i=l,j=mid+1;while(i<=mid && j<=r){if(q[i]<=q[j]) tmp[k++]=q[i++];else{tmp[k++]=q[j++];ans+=mid-i+1;}}while(i<=mid) tmp[k++]=q[i++];while(j<=r) tmp[k++]=q[j++];for(i=l,j=0;i<=r;i++,j++)q[i]=tmp[j];
}
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for(int i=0;i<n;i++) cin>>lst[i];merge(lst,0,n-1);cout<<ans<<"\n";return 0;
}

P1966 [NOIP 2013 提高组] 火柴排队

//树状数组计算逆序对
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5,mod=1e8-3;
int n,tr[N],p[N];
struct node{int x,pos;
}a[N],b[N];
bool cmp(node a,node b){return a.x<b.x;
}
int lowbit(int x)
{return x&-x;
}
void updata(int x,int v)
{for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=v;
}
int sum(int x)
{int res=0;for(int i=x;i>=1;i-=lowbit(i)) res+=tr[i];return res;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n;for(int i=1;i<=n;i++) cin>>a[i].x,a[i].pos=i;for(int i=1;i<=n;i++) cin>>b[i].x,b[i].pos=i;sort(a+1,a+1+n,cmp),sort(b+1,b+1+n,cmp);for(int i=1;i<=n;i++) p[a[i].pos]=b[i].pos;int ans=0;for(int i=1;i<=n;i++){updata(p[i],1);ans=(ans+i-sum(p[i]))%mod;}cout<<ans<<endl;return 0;
}

P2345 [USACO04OPEN] MooFest G

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e4 + 10;
int max_coor;
struct node{int v,x;
}a[maxn];
ll sum[maxn];  //坐标的累加和
ll num[maxn];  //坐标的出现次数
int n;
int lowbit(int x){return x & -x;
}
bool cmp(node x,node y){return x.v < y.v;
}
void update_sum(int i,int val)
{for(;i<=max_coor;i+=lowbit(i)) sum[i]+=val;
}
//更新坐标计数树状数组
void update_num(int i)
{for(;i<=max_coor;i+=lowbit(i)) num[i]++;
}
//查询坐标区间[l,r]的累加和
ll query_sum(int l,int r)
{ll ans=0;for(;r>=1;r-=lowbit(r))ans+=sum[r];for(l--;l>=1;l-=lowbit(l))ans-=sum[l];return ans;
}
//查询坐标区间[l,r]的点的数量
ll query_num(int l,int r)
{ll ans=0;for(;r>=1;r-=lowbit(r))ans+=num[r];for(l--;l>=1;l-=lowbit(l))ans-=num[l];return ans;
}
int main()
{cin>>n;ll ans=0;for(int i=1;i<=n;i++){cin>>a[i].v>>a[i].x;max_coor=max(max_coor,a[i].x);}sort(a+1,a+1+n,cmp);  //按照听力值从小到大排序for(int i=1;i<=n;i++){update_sum(a[i].x,a[i].x);  //将当前坐标累加到sum树状数组update_num(a[i].x);         //将当前坐标计数加1ans+=a[i].v*(query_sum(a[i].x+1,max_coor)-a[i].x*query_num(a[i].x+1,max_coor));ans+=a[i].v*(a[i].x*query_num(1,a[i].x-1)-query_sum(1,a[i].x-1));}cout<<ans<<endl;return 0;
}

P1438 无聊的数列

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
ll n,m,a[N],d[N],bit1[N],bit2[N];
ll lowbit(ll x)
{return x&(-x);
}
void updata(ll x,ll y)
{ll id=x;for(;x<=n;x+=lowbit(x)){bit1[x]+=y;bit2[x]+=y*id;}
}
ll query(ll x)
{ll id=x,sum=0;while(x){sum+=(id+1)*bit1[x]-bit2[x];x-=lowbit(x);}return sum;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;for(ll i=1;i<=n;i++){cin>>a[i];d[i]=a[i]-a[i-1];updata(i,d[i]-d[i-1]);}for(ll i=1;i<=m;i++){int op;cin>>op;if(op==1){ll l,r,K,D;cin>>l>>r>>K>>D;updata(l,K);updata(l+1,D-K);updata(r+1,-(r-l+1)*D-K);updata(r+2,K+(r-l)*D);}else{ll p;cin>>p;printf("%lld\n",query(p));}}return 0;
}

P2344 [USACO11FEB] Generic Cow Protests G

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=1e9+9;
const int N=1e5+5;
ll dp[N];       // dp[i]: 前i头奶牛的分组方案数
ll tree[N];     // 树状数组，用于维护dp的前缀和
ll haxi[N];     // 离散化后的排名
ll n,pre[N],pre_sort[N],len=0;
int lowbit(int x)
{return x&(-x);
}
// 树状数组查询函数：求<= x的所有元素的和
ll query_sum(ll x)
{ll sum=0;while(x){sum+=tree[x];sum%=mod;x-=lowbit(x);}return sum;
}
// 树状数组更新函数：在位置x增加val
void update(ll x,ll val)
{while(x<=len){tree[x]+=val;tree[x]%=mod;x+=lowbit(x);}
}
int main()
{cin>>n;for(ll i=1;i<=n;i++){cin>>pre[i];pre[i]+=pre[i-1]; //计算前缀和pre_sort[i]=pre[i];}sort(pre_sort,pre_sort+1+n);len=unique(pre_sort,pre_sort+1+n)-pre_sort;for(int i=0;i<=n;i++) haxi[i]=lower_bound(pre_sort,pre_sort+len,pre[i])-pre_sort+1;update(haxi[0],1);  for(ll i=1;i<=n;i++){dp[i]=query_sum(haxi[i]); //查询满足pre[j]<=pre[i]的dp[j]的和update(haxi[i],dp[i]);    //将当前dp[i]加入树状数组}cout<<dp[n];return 0;
}

P5057 [CQOI2006] 简单题

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+5;
LL n,m;
LL cnt[N];  //查分数组 
LL a[N];
int lowbit(int x)
{return x&(-x);
}
void updata(LL x,LL d)
{while(x<=n){cnt[x]+=d;x+=lowbit(x);}
}
LL sum(LL x)
{LL res=0;while(x>0){res+=cnt[x];x-=lowbit(x);}return res;
} 
int main(void)
{ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n>>m;while(m--){LL opt,l,r,x;cin>>opt;if(opt==1){cin>>l>>r;updata(l,1);updata(r+1,-1);}else{cin>>x;LL k=sum(x);if(k%2==0) cout<<0<<endl;else cout<<1<<endl;}}return 0;
}

欢迎大家指正