目錄

• 1264. 動態求連續區間和 【樹狀數組板子題】
• 1265. 數星星 【樹狀數組變種】
• 1270. 數列區間最大值 【線段樹 / 區間內求最大值】
• 1215. 小朋友排隊 【樹狀數組】
• AcWing 1228. 油漆面積 【掃描線】
• AcWing 1232. 三體攻擊 【不會 三維差分】
• AcWing 1237. 螺旋折線 【找規律】
• 797. 差分 【板子題】
• 798. 差分矩陣 【板子題】

1264. 動態求連續區間和 【樹狀數組板子題】

樹狀數組解法:

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,m,a[N],tr[N]; int lowbit(int x) {return x & -x; } void add(int x,int v) {for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=v; } int query(int x) {int res=0;for(int i=x;i;i-=lowbit(i)) res+=tr[i]; return res; } int main(void) {scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++) add(i,a[i]);while(m--){int k,x,y;scanf("%d%d%d",&k,&x,&y);if(k==0) printf("%d\n",query(y)-query(x-1));else add(x,y);}return 0; }

線段樹寫法:

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,m; int w[N]; struct Node {int l,r;int sum; }tr[N*4]; void pushup(int u) {tr[u].sum=tr[u<<1].sum+tr[u<<1 | 1].sum; } void build(int u,int l,int r) {if(l==r) tr[u]={l,r,w[r]};else{tr[u]={l,r};int mid=(l+r)>>1;build(u<<1,l,mid),build(u<<1 | 1,mid+1,r);pushup(u);} } int query(int u,int l,int r) {if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;int mid=(tr[u].l+tr[u].r)>>1;int sum=0;if(l<=mid) sum=query(u<<1,l,r);if(r>mid) sum+=query(u<<1 | 1,l,r);return sum; } void modify(int u,int x,int v) {if(tr[u].l==tr[u].r) tr[u].sum+=v;else{int mid=(tr[u].l+tr[u].r)>>1;if(x<=mid) modify(u<<1,x,v);else modify(u<<1 | 1,x,v);pushup(u);} } int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) cin>>w[i];build(1,1,n);int k,a,b;while(m--){cin>>k>>a>>b;if(k==0) printf("%d\n",query(1,a,b));else modify(1,a,b);}return 0; }

1265. 數星星 【樹狀數組變種】

#include<bits/stdc++.h> using namespace std; const int N=32005; int tr[N],n,st[N]; int lowbit(int x) {return x & -x; } void add(int x) {for(int i=x;i<N;i+=lowbit(i)) tr[i]++; } int query(int x) {int res=0;for(int i=x;i;i-=lowbit(i)) res+=tr[i];return res; } int main(void) {cin>>n;for(int i=0;i<n;i++){int x,y; cin>>x>>y;x++;st[query(x)-query(0)]++;add(x);}for(int i=0;i<n;i++) cout<<st[i]<<endl;return 0; }

1270. 數列區間最大值 【線段樹 / 區間內求最大值】

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,m; int w[N]; struct Node {int l,r;int sum; }tr[N*4]; void pushup(int u) {tr[u].sum=max(tr[u<<1].sum,tr[u<<1 | 1].sum); } void build(int u,int l,int r) {if(l==r) tr[u]={l,r,w[r]};else{tr[u]={l,r};int mid=(l+r)>>1;build(u<<1,l,mid),build(u<<1 | 1,mid+1,r);pushup(u);} } int query(int u,int l,int r) {if(tr[u].l>=l&&tr[u].r<=r) return tr[u].sum;int mid=(tr[u].l+tr[u].r)>>1;int sum=0;if(l<=mid) sum=query(u<<1,l,r);if(r>mid) sum=max(sum,query(u<<1 | 1,l,r));return sum; } int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d",&w[i]);build(1,1,n);int a,b;while(m--){scanf("%d%d",&a,&b);printf("%d\n",query(1,a,b));}return 0; }

1215. 小朋友排隊 【樹狀數組】

每個數所對應的換位次數（逆序對）=前面比它大的+后面比它小的 樹狀數組維護的是每一個身高所對應的個數 #include<bits/stdc++.h> using namespace std; typedef long long int LL; const int N=1e6+10; int n; int h[N],tr[N]; int sum[N]; int lowbit(int x) {return x&-x; } void add(int x,int v) {for(int i=x;i<N;i+=lowbit(i)) tr[i]+=v; } int query(int x) {int res=0;for(int i=x;i;i-=lowbit(i)) res+=tr[i];return res; } int main(void) {scanf("%d",&n);for(int i=0;i<n;i++) scanf("%d",&h[i]),h[i]++;for(int i=0;i<n;i++){sum[i]=query(N-1)-query(h[i]);add(h[i],1);}memset(tr,0,sizeof tr);for(int i=n-1;i>=0;i--){sum[i]+=query(h[i]-1);add(h[i],1);}LL res=0;for(int i=0;i<n;i++) res+=sum[i]*(sum[i]+1ll)/2;cout<<res;return 0; } #include<bits/stdc++.h> using namespace std; const int N=1e6+10; typedef unsigned long long int LL; LL h[N],st[N],n; int tr1[N],tr2[N]; int lowbit(int x){return x&(-x);} void add(int tr[],int x,int v) {for(int i=x;i<N;i+=lowbit(i)) tr[i]+=v; } int query(int tr[],int x) {int sum=0;for(int i=x;i;i-=lowbit(i)) sum+=tr[i];return sum; } int main(void) {cin>>n;for(int i=1;i<=n;i++) cin>>h[i],h[i]++,st[h[i]]++;for(int i=1;i<N;i++) add(tr2,i,st[i]);for(int i=1;i<=n;i++){add(tr2,h[i],-1);st[i]=query(tr1,N-1)-query(tr1,h[i])+query(tr2,h[i]-1);//前面比它大的，后面比他小的。add(tr1,h[i],1);}LL ans=0;for(int i=1;i<=n;i++) ans+=1ll*st[i]*(st[i]+1)/2;cout<<ans;return 0; }

AcWing 1228. 油漆面積 【掃描線】

#include<bits/stdc++.h> using namespace std; const int N=1e5*3+10; int n; struct Segment {double x,y1,y2;bool operator< (const Segment &t)const{return x<t.x;}int k; }seg[N*2]; struct Node {int l,r;int cnt;//當前區間被覆蓋的次數double len;//子區間總共被覆蓋的長度 }tr[N*8]; vector<double>ys;int find(double y) {return lower_bound(ys.begin(),ys.end(),y)-ys.begin(); }void pushup(int u) {if(tr[u].cnt) tr[u].len=ys[tr[u].r+1]-ys[tr[u].l];else if(tr[u].l!=tr[u].r){tr[u].len=tr[u*2].len+tr[u*2+1].len; }else tr[u].len=0; }void build(int u,int l,int r) {tr[u]={l,r,0,0};if(l!=r){int mid=(l+r)/2;build(u*2,l,mid),build(u*2+1,mid+1,r);} }void modify(int u,int l,int r,int k) {if(l<=tr[u].l&&tr[u].r<=r){tr[u].cnt+=k;pushup(u);}else{int mid=(tr[u].l+tr[u].r)/2;if(l<=mid) modify(u*2,l,r,k);if(r>mid) modify(u*2+1,l,r,k);pushup(u);} }int main() {cin>>n;for(int i=0,j=0;i<n;i++){double x1,y1,x2,y2; scanf("%lf%lf%lf%lf",&x1,&y1,&x2,&y2);seg[j++]={x1,y1,y2,1};seg[j++]={x2,y1,y2,-1};ys.push_back(y1),ys.push_back(y2);}sort(ys.begin(),ys.end());ys.erase(unique(ys.begin(),ys.end()),ys.end());build(1,0,ys.size()-2);sort(seg,seg+n*2);long long int res=0;for(int i=0;i<n*2;i++){if(i>0) res+=tr[1].len*(seg[i].x-seg[i-1].x);modify(1,find(seg[i].y1),find(seg[i].y2)-1,seg[i].k);}printf("%lld",res); }

AcWing 1232. 三體攻擊 【不會 三維差分】

AcWing 1237. 螺旋折線 【找規律】

#include<cstdio> #include<cmath> #include<iostream> using namespace std; int x; int y; long long ans; int main(void) {cin>>x>>y;if(abs(x)<=y&&y>=0)//上{if(x>=0)ans=(long long)(2*y)*(2*y)-(y-x);elseans=(long long)(2*y)*(2*y-1)+(y-abs(x));}if(abs(y)<=x&&x>=0)//左{if(y>=0)ans=(long long)(2*x)*(2*x)+(x-y);elseans=(long long)(2*x)*(2*x+1)-(x-abs(y));}if(abs(x)<=abs(y)+1&&y<0)//下{if(x>=0)ans=(long long)(2*abs(y))*(2*abs(y)+1)+(abs(y)-x);elseans=(long long)(2*(abs(y)+1)-1)*(2*(abs(y)+1)-1)-(abs(y)+1-abs(x));}if(abs(y)<=abs(x)-1&&x<0)//右{if(y>=0)ans=(long long)(2*abs(x))*(2*abs(x)-1)-(abs(x)-y);elseans=(long long)(2*abs(x)-1)*(2*abs(x)-1)+(abs(x)-1-abs(y));}cout<<ans<<endl;return 0; }

797. 差分 【板子題】

#include<bits/stdc++.h> using namespace std; const int N=1e6+10; int a[N],b[N],n,m; void insert(int l,int r,int c) {b[l]+=c;b[r+1]-=c; } int main(void) {cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i],insert(i,i,a[i]);while(m--){int l,r,c; cin>>l>>r>>c;insert(l,r,c);}for(int i=1;i<=n;i++) b[i]+=b[i-1],cout<<b[i]<<" ";return 0; }

798. 差分矩陣 【板子題】

#include<bits/stdc++.h> using namespace std; const int N=1010; int a[N][N],b[N][N],n,m,k; void insert(int x,int y,int xx,int yy,int c) {b[x][y]+=c;b[xx+1][y]-=c;b[x][yy+1]-=c;b[xx+1][yy+1]+=c; } int main(void) {cin>>n>>m>>k;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)cin>>a[i][j],insert(i,j,i,j,a[i][j]);while(k--){int x,y,xx,yy,c; cin>>x>>y>>xx>>yy>>c;insert(x,y,xx,yy,c);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){b[i][j]=b[i-1][j]+b[i][j-1]-b[i-1][j-1]+b[i][j];cout<<b[i][j]<<" ";}cout<<endl;} }

總結

以上是生活随笔為你收集整理的第五讲 树状数组与线段树 【未完结】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。