-
树状数组与线段树模板集合
前言
马上就要 csp \texttt{csp} csp了， 树状数组和线段树肯定是复习不可少的一部分。今天作者来整理一下它们的模板。
线段树
I. \texttt{I.} I.单点修改，区间查询。
例题：P3374
代码：#includeusing namespace std; #define lid id*2 #define rid id*2+1 const int N=5e6+7; int n,m; int a[N]; struct sa{ int l; int r; int sum; }tree[N<<1]; void build(int id,int l,int r){ tree[id].l=l,tree[id].r=r; if(l==r){ tree[id].sum=a[l]; return; } int mid=(l+r)>>1; build(lid,l,mid); build(rid,mid+1,r); tree[id].sum=tree[lid].sum+tree[rid].sum; return; } int search(int id,int l,int r){ if(tree[id].l>r||tree[id].r<l)return 0; if(tree[id].l>=l&&tree[id].r<=r){ return tree[id].sum; } int s=0; if(tree[lid].r>=l){ s+=search(lid,l,r); } if(tree[rid].l<=r){ s+=search(rid,l,r); } return s; } void add(int id,int x,int w){ if(tree[id].l==tree[id].r){ tree[id].sum+=w; return; } int mid=(tree[id].l+tree[id].r)>>1; if(x<=mid)add(lid,x,w); else add(rid,x,w); tree[id].sum=tree[lid].sum+tree[rid].sum; return; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; build(1,1,n); while(m--){ int op,x,y; cin>>op>>x>>y; if(op==1){ add(1,x,y); } else{ cout<<search(1,x,y)<<'\n'; } } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
II. \texttt{II.} II.区间修改，单点查询。
例题：P3368
代码：#includeusing namespace std; void sleep(int p);int read();int read(int p); #define ll long long #define ull unsigned long long #define db double #define lid id*2 #define rid id*2+1 const int N=3e6+7,inf=0x3f3f3f3f,mod=1e9+7; struct sa{ int sum; int l,r; }tree[N]; int n,ans; int a[N]; void build(int id,int l,int r){ tree[id].l=l,tree[id].r=r; if(l==r){ tree[id].sum=a[l]; return ; } int mid=l+r>>1; build(lid,l,mid); build(rid,mid+1,r); return; } void modify(int id,int l,int r,int k){ if(tree[id].l>=l&&tree[id].r<=r){ tree[id].sum+=k; return; } if(tree[id].l>r||tree[id].r<l)return; int mid=tree[id].l+tree[id].r>>1; if(mid>=l)modify(lid,l,r,k); if(mid<r)modify(rid,l,r,k); return; } void query(int id,int dis){ ans+=tree[id].sum; if(tree[id].l==tree[id].r) return; int mid=tree[id].l+tree[id].r>>1; if(dis<=mid)query(lid,dis); else query(rid,dis); return ; } int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); int n,m; cin>>n>>m; for(int i=1;i<=n;i++)cin>>a[i]; build(1,1,n); while(m--){ int c; cin>>c; if(c==1){ int x,y,z; cin>>x>>y>>z; modify(1,x,y,z); } else{ ans=0; int x;cin>>x; query(1,x); cout<<ans<<'\n'; } } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
III. \texttt{III.} III.区间修改，区间查询
例题：P3372
代码：#includeusing namespace std; #define lid id*2 #define rid id*2+1 const long long N=5e5+7; long long n,m; long long a[N]; struct sa{ long long l,r,sum; long long lz; }tree[N]; void build(long long id,long long l,long long r){ tree[id].l=l,tree[id].r=r,tree[id].lz=0; if(l==r){ tree[id].sum=a[l]; return; } long long mid=l+r>>1; build(lid,l,mid); build(rid,mid+1,r); tree[id].sum=tree[lid].sum+tree[rid].sum; return; } void push_down(long long id){ if(!tree[id].lz)return ; long long mid=tree[id].l+tree[id].r>>1; tree[lid].lz+=tree[id].lz; tree[lid].sum+=(mid-tree[id].l+1)*tree[id].lz; tree[rid].lz+=tree[id].lz; tree[rid].sum+=(tree[rid].r-mid)*tree[id].lz; tree[id].lz=0; return; } void update(long long id,long long l,long long r,long long k){ if(tree[id].r<=r&&tree[id].l>=l){ tree[id].sum+=k*(tree[id].r-tree[id].l+1); tree[id].lz+=k; return; } push_down(id); long long mid=tree[id].l+tree[id].r>>1; if(l<=mid)update(lid,l,r,k); if(mid<r)update(rid,l,r,k); tree[id].sum=tree[lid].sum+tree[rid].sum; return; } long long search(long long id,long long l,long long r){ if(tree[id].l>=l&&tree[id].r<=r) return tree[id].sum; if(tree[id].r<l|tree[id].l>r)return 0; push_down(id); long long s=0; if(tree[lid].r>=l)s+=search(lid,l,r); if(tree[rid].l<=r)s+=search(rid,l,r); return s; } int main(){ cin>>n>>m; for(long long i=1;i<=n;i++)cin>>a[i]; build(1,1,n); while(m--){ long long x,y,z,k; cin>>x>>y>>z; if(x==1){ cin>>k; update(1,y,z,k); } else{ cout<<search(1,y,z)<<'\n'; } } return 0; } - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
IV. \texttt{IV.} IV.区间加法、乘法，区间查询。
例题：P3373
代码：#includeusing namespace std; void sleep(int p);long long read();int read(long long p); #define lid id*2 #define rid id*2+1 typedef long long ll; #define ull unsigned long long #define db double const int N=5e5+5,inf=0x3f3f3f3f,mod=1e9+7; int n,m; ll p; ll a[N]; struct sa{ ll l,r; ll sum,add,mul; }tree[N]; inline void init(int id){ tree[id].sum%=p,tree[id].mul%=p,tree[id].sum%=p; return; } void build(int id,ll l,ll r){ tree[id].l=l,tree[id].r=r,tree[id].mul=1; if(l==r){ tree[id].sum=a[l]%p; return; } int mid=tree[id].l+tree[id].r>>1; build(lid,l,mid);build(rid,mid+1,r); tree[id].sum=tree[lid].sum+tree[rid].sum; tree[id].sum%=p; return; } void push_down(int id){ int mul=tree[id].mul,add=tree[id].add; tree[lid].sum=tree[lid].sum*mul+add*(tree[lid].r-tree[lid].l+1); tree[rid].sum=tree[rid].sum*mul+add*(tree[rid].r-tree[rid].l+1); tree[lid].mul*=mul,tree[rid].mul*=mul; tree[lid].add=(tree[lid].add*mul+add)%p; tree[rid].add=(tree[rid].add*mul+add)%p; tree[id].mul=1,tree[id].add=0; init(lid),init(rid); return; } void update(int id,bool op,ll l,ll r,ll k){ if(tree[id].l>=l&&tree[id].r<=r){ if(op){ tree[id].mul*=k; tree[id].add*=k; tree[id].sum*=k; init(id); } else{ tree[id].sum+=(tree[id].r-tree[id].l+1)*k%p; tree[id].add+=k; init(id); } return; } push_down(id); ll mid=tree[id].l+tree[id].r>>1; if(mid>=l)update(lid,op,l,r,k); if(mid+1<=r)update(rid,op,l,r,k); tree[id].sum=(tree[lid].sum+tree[rid].sum)%p; return; } ll query(int id,int l,int r){ if(tree[id].l>=l&&tree[id].r<=r){ return tree[id].sum; } if(tree[id].l>r||tree[id].r<l)return 0; push_down(id); int mid=tree[id].l+tree[id].r>>1;ll s=0; if(mid>=l)s+=query(lid,l,r); if(mid+1<=r)s+=query(rid,l,r); return s%p; } int main() { cin>>n>>m>>p; for(int i=1;i<=n;i++){ a[i]=read();a[i]%=p; } build(1,1,n); while(m--){ ll x=read(),y=read(),z=read(),k; if(x==1){ k=read();k%=p; update(1,1,y,z,k); }else if(x==2){ k=read();k%=p; update(1,0,y,z,k); }else{ printf("%lld\n",query(1,y,z)); } } return 0; } void sleep(int p){for(int i=1;i<=p*100000;i++)int x;return;} inline long long read(){long long x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;} inline int read(long long p){long long x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();x=x%p;}return x*f;} - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
树状数组
I. \texttt{I.} I.单点修改，区间查询。
例题：P3374
代码：#includeusing namespace std; #define ll long long #define ull unsigned long long const int N=6e5+5,mod=1e9+7; inline void sleep(int p); inline int read(); inline int read(int mod); int n,m; int a[N]; int c[N]; int lbt(int x){return x & -x;} void add(int x,int k){ for(;x<=n;x+=lbt(x))c[x]+=k; return; } int ask(int x){ int t=0; for(;x;x-=lbt(x))t+=c[x]; return t; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; add(i,a[i]); } while(m--){ int op; cin>>op; if(op==1){ int x,k; cin>>x>>k; add(x,k); } else{ int l,r; cin>>l>>r; cout<<ask(r)-ask(l-1)<<'\n'; } } return 0; } inline void sleep(int p){for(int i=1;i<=100000*p;i++)int x;return;} inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;} inline int read(int p){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();x=x%p;}return x*f;} - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
II. \texttt{II.} II.区间修改，单点查询。
例题：P3368
代码：#includeusing namespace std; #define ll long long #define ull unsigned long long const int N=6e5+5,mod=1e9+7; inline void sleep(int p); inline int read(); inline int read(int mod); int n,m; int a[N]; int b[N]; int c[N]; int lbt(int x){return x & -x;} void add(int x,int k){ for(;x<=n;x+=lbt(x))c[x]+=k; return; } int ask(int x){ int t=0; for(;x;x-=lbt(x))t+=c[x]; return t; } int main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; b[i]=a[i]-a[i-1]; add(i,b[i]); } while(m--){ int op; cin>>op; if(op==1){ int l,r,x; cin>>l>>r>>x; add(l,x); if(r<n)add(r+1,-x); } else{ int l; cin>>l; cout<<ask(l)<<'\n'; } } return 0; } inline void sleep(int p){for(int i=1;i<=100000*p;i++)int x;return;} inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;} inline int read(int p){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();x=x%p;}return x*f;} - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
III. \texttt{III.} III.区间修改，区间查询。
例题：P3372
代码：#includeusing namespace std; #define ll long long #define ull unsigned long long #define int long long const int N=7e5+5,mod=1e9+7; inline void sleep(int p); inline int read(); inline int read(int mod); int n,m; int a[N]; int b[N]; int c[2][N]; void add(int op,int x,int k){ for(;x<=n;x+=x&-x)c[op][x]+=k; return; } int ask(int op,int x){ int t=0; for(;x;x-=x&-x)t+=c[op][x]; return t; } signed main(){ cin>>n>>m; for(int i=1;i<=n;i++){ cin>>a[i]; b[i]=b[i-1]+a[i]; } while(m--){ int op; cin>>op; if(op==1){ int l,r,d; cin>>l>>r>>d; add(0,l,d); add(0,r+1,-d); add(1,l,d*l); add(1,r+1,-d*(r+1)); } else{ int l,r; cin>>l>>r; int ans=b[r]+(r+1)*ask(0,r)-ask(1,r); ans-=b[l-1]+l*ask(0,l-1)-ask(1,l-1); cout<<ans<<'\n'; } } return 0; } inline void sleep(int p){for(int i=1;i<=100000*p;i++)int x;return;} inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;} inline int read(int p){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();x=x%p;}return x*f;} - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
结语
希望大家看了这篇博文后，能有更多的进步。如果想进一步提升 OI \texttt{OI} OI 水平，可以做一下这道题，本人原创。
-
相关阅读:
仪表基础知识培训
基于微信小程序的日语学习的系统，附源码
webpack打包
Matlab：在文本和值之间转换datetimeduration
RabbitMQ与Spring Boot如何集成？
C++运算符重载
跟我学c++中级篇——初等字符串转化初
mac m1 docker安装nacos
【C++进阶】map和set（ 万字详解）—— 上篇
【Spring】一文带你吃透基于XML的DI技术
- 原文地址：https://blog.csdn.net/yyf525/article/details/125864298
