这里主要收录一些数据结构的模板
啊我还是太弱了居然要收录模板
1.树状数组
1 //树状数组 2 int a[],t[]//原数组，对应的树状数组 3 int lowbit(int x) 4 { 5 return x&(-x); 6 } 7 void modify(int x,int y)//单点修改a[x]加上y 8 { 9 for(int i=x;i<=n;i+=lowbit(i)) 10 { 11 t[i]+=y; 12 } 13 } 14 int query(int x)//区间求和a[1]....a[x] 15 { 16 int ans=0; 17 for(int i=x;i>=1;i-=lowbit(i)) 18 { 19 ans+=t[i]; 20 } 21 return ans; 22 } 23 int sum(int l,int r)//区间求和a[l]....a[r] 24 { 25 return query(r)-query(l-1); 26 }
以及稍稍的变种
1 //区间修改，单点查询的树状数组，利用差分思想 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<algorithm> 7 using namespace std; 8 int a[1000001],b[1000001]; 9 int m,n,x,y,z,q; 10 int lowbit(int x) 11 { 12 return x&(-x); 13 } 14 void add(int x,int y) 15 { 16 for(int i=x;i<=n;i+=lowbit(i)) 17 a[i]+=y; 18 } 19 int sum(int s) 20 { 21 int ans=0; 22 for(int i=s;i>=1;i-=lowbit(i)) 23 { 24 ans+=a[i]; 25 } 26 return ans; 27 } 28 int main() 29 { 30 cin>>n>>m; 31 for(int i=1;i<=n;i++) 32 cin>>b[i]; 33 for(int i=1;i<=m;i++) 34 { 35 cin>>x; 36 if(x==1) 37 { 38 cin>>y>>z>>q; 39 add(y,q); 40 add(z+1,-q); 41 } 42 if(x==2) 43 { 44 cin>>y; 45 printf("%lld\n",b[y]+sum(y)); 46 } 47 48 } 49 }
2.线段树
1 struct pp 2 { 3 int l,r; 4 int sum; 5 int tag; 6 }f[]; 7 void up(int rt) 8 { 9 f[rt].sum=f[rt<<1].sum+f[rt<<1|1].sum; 10 } 11 void down(int rt) 12 { 13 if(f[rt].tag) 14 { 15 f[rt<<1].sum+=f[rt].tag*(f[rt<<1].r-f[rt<<1].l+1); 16 f[rt<<1|1].sum+=f[rt].tag*(f[rt<<1|1].r-f[rt<<1|1].l+1); 17 f[rt<<1].tag+=f[rt].tag; 18 f[rt<<1|1].tag+=f[rt].tag; 19 f[rt].tag=0; 20 } 21 } 22 void build(int rt,int l,int r) 23 { 24 f[rt].l=l; 25 f[rt].r=r; 26 if(l==r) 27 { 28 f[rt].sum=a[l]; 29 return; 30 } 31 int mid=(l+r)>>1; 32 build(rt<<1,l,mid); 33 build(rt<<1|1,mid+1,r); 34 up(rt); 35 } 36 void modify(int rt,int x,int y) 37 { 38 if(f[rt].l==f[rt].r) 39 { 40 f[rt].sum+=y; 41 return; 42 } 43 int mid=(f[rt].l+f[rt].r)>>1; 44 if(x<=mid) modify(rt<<1,x,y); 45 else/*if(x>mid)*/ modify(rt<<1|1,x,y); 46 up(rt); 47 } 48 void add(int rt,int l,int r,int k) 49 { 50 if(l<=f[rt].l&&f[rt].r<=r) 51 { 52 f[rt].sum+=k*(f[rt].r-f[rt].l+1); 53 f[rt].tag+=k; 54 return; 55 } 56 int ans=0; 57 down(rt); 58 int mid=(f[rt].l+f[rt].r)>>1; 59 if(l<=mid) add(rt<<1,l,r,k); 60 if(r>mid) add(rt<<1|1,l,r,k); 61 up(rt); 62 } 63 int query(int rt,int l,int r) 64 { 65 if(l<=f[rt].l&&f[rt].r<=r) 66 { 67 return f[rt].sum; 68 } 69 down(rt); 70 int ans=0; 71 int mid=(f[rt].l+f[rt].r)>>1; 72 if(l<=mid) ans+=query(rt<<1,l,r); 73 if(r>mid) ans+=query(rt<<1|1,l,r); 74 return ans; 75 }
以及线段树的区间乘法
1 //线段树取模与区间乘法LAZYTAG 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 #include<iostream> 7 using namespace std; 8 struct pp 9 { 10 int l,r; 11 long long sum,add,mul; 12 }f[5000005]; 13 int a[1000001]; 14 int x,y,z,k,n,m,p; 15 void up(int rt) 16 { 17 f[rt].sum=(f[rt<<1].sum+f[rt<<1|1].sum)%p; 18 } 19 void down(int rt) { 20 if(f[rt].add!=0||f[rt].mul!=1) { 21 int mid = (f[rt].l + f[rt].r) >> 1; 22 f[rt<<1].sum=(f[rt<<1].sum*f[rt].mul+f[rt].add*(mid-f[rt].l+1))%p; 23 f[rt<<1|1].sum=(f[rt<<1|1].sum*f[rt].mul+f[rt].add*(f[rt].r-mid))%p; 24 f[rt<<1].mul=(f[rt<<1].mul*f[rt].mul)%p; 25 f[rt<<1|1].mul=(f[rt<<1|1].mul*f[rt].mul)%p; 26 f[rt<<1].add=(f[rt<<1].add*f[rt].mul+f[rt].add)%p; 27 f[rt<<1|1].add=(f[rt<<1|1].add*f[rt].mul+f[rt].add)%p; 28 f[rt].add=0; 29 f[rt].mul=1; 30 } 31 } 32 33 //void down(int rt) 34 //{ 35 // if(f[rt].add!=0||f[rt].mul!=1) 36 // { 37 // f[rt<<1].sum=(f[rt<<1].sum*f[rt].mul+f[rt].add*(f[rt].r-f[rt].l+1))%p; 38 // f[rt<<1|1].sum=(f[rt<<1|1].sum*f[rt].mul+f[rt].add*(f[rt].r-f[rt].l+1))%p; 39 // f[rt<<1].mul=(f[rt<<1].mul*f[rt].mul)%p; 40 // f[rt<<1|1].mul=(f[rt<<1|1].mul*f[rt].mul)%p; 41 // f[rt<<1].add=(f[rt<<1].add*f[rt].mul+f[rt].add)%p; 42 // f[rt<<1|1].add=(f[rt<<1|1].add*f[rt].mul+f[rt].add)%p; 43 // f[rt].add=0; 44 // f[rt].mul=1; 45 // } 46 //} 47 void build(int rt,int l,int r) 48 { 49 f[rt].add=0; 50 f[rt].mul=1; 51 f[rt].l=l; 52 f[rt].r=r; 53 if(l==r){ 54 f[rt].sum=a[l]; 55 return ; 56 57 } 58 int mid=(l+r)>>1; 59 build(rt<<1,l,mid); 60 build(rt<<1|1,mid+1,r); 61 up(rt); 62 } 63 void mult(int rt,int l,int r,int k) 64 { 65 if(l<=f[rt].l&&r>=f[rt].r) 66 { 67 f[rt].sum=(f[rt].sum*k)%p; 68 f[rt].mul=(f[rt].mul*k)%p; 69 f[rt].add=(f[rt].add*k)%p; 70 return; 71 } 72 down(rt); 73 int mid=(f[rt].l+f[rt].r)>>1; 74 if(l<=mid) mult(rt<<1,l,r,k); 75 if(r>mid) mult(rt<<1|1,l,r,k); 76 up(rt); 77 } 78 void quer(int rt,int l,int r,int k) 79 { 80 if(l<=f[rt].l&&r>=f[rt].r) 81 { 82 f[rt].sum=(f[rt].sum+k*(f[rt].r-f[rt].l+1))%p; 83 f[rt].add=(f[rt].add+k)%p; 84 return; 85 } 86 down(rt); 87 int mid=(f[rt].l+f[rt].r)>>1; 88 if(l<=mid) quer(rt<<1,l,r,k); 89 if(r>mid) quer(rt<<1|1,l,r,k); 90 up(rt); 91 } 92 long long sum (int rt,int l,int r) 93 { 94 if(l<=f[rt].l&&r>=f[rt].r){ 95 return f[rt].sum%p; 96 } 97 down(rt); 98 long long ans=0; 99 100 int mid=(f[rt].r+f[rt].l)>>1; 101 if(l<=mid) ans+=sum(rt<<1,l,r); 102 if(mid<r) ans+=sum(rt<<1|1,l,r); 103 return ans%p; 104 } 105 int main(){ 106 107 scanf("%d%d%d",&n,&m,&p); 108 for(int i=1;i<=n;i++) 109 scanf("%d",&a[i]); 110 build(1,1,n); 111 for(int i=1;i<=m;i++){ 112 scanf("%d",&x); 113 if(x==1){ 114 scanf("%d%d%d",&y,&z,&k); 115 mult(1,y,z,k); 116 } 117 else if(x==2){ 118 scanf("%d%d%d",&y,&z,&k); 119 quer(1,y,z,k); 120 } 121 else{ 122 scanf("%d%d",&y,&z); 123 cout<<sum(1,y,z)<<endl; 124 } 125 } 126 return 0; 127 }
3.树链剖分
这里用线段树来维护并操作树剖
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <cmath> 6 using namespace std; 7 const int MAXN=200010; 8 struct pp 9 { 10 int u; 11 int nex; 12 }e[MAXN]; 13 struct oo 14 { 15 int l,r; 16 int sum,tag; 17 }s[MAXN]; 18 int n,m,cnt,g,mod,res,num; 19 int head[MAXN],a[MAXN],wt[MAXN]; 20 int id[MAXN],son[MAXN],dep[MAXN],sz[MAXN],top[MAXN],fa[MAXN]; 21 void add(int x ,int y) 22 { 23 e[++cnt].u=y; 24 e[cnt].nex=head[x]; 25 head[x]=cnt; 26 } 27 // 线段树 28 void up(int rt) 29 { 30 s[rt].sum=(s[rt<<1].sum+s[rt<<1|1].sum)%mod; 31 } 32 void down(int rt) 33 { 34 if(s[rt].tag) 35 { 36 s[rt<<1].sum=(s[rt<<1].sum+s[rt].tag*(s[rt<<1].r-s[rt<<1].l+1))%mod; 37 s[rt<<1|1].sum=(s[rt<<1|1].sum+s[rt].tag*(s[rt<<1|1].r-s[rt<<1|1].l+1))%mod; 38 s[rt<<1].tag=(s[rt<<1].tag+s[rt].tag)%mod; 39 s[rt<<1|1].tag=(s[rt<<1|1].tag+s[rt].tag)%mod; 40 s[rt].tag=0; 41 } 42 } 43 void build(int rt,int l,int r) 44 { 45 s[rt].l=l; 46 s[rt].r=r; 47 if(l==r) 48 { 49 s[rt].sum=a[l]; 50 return; 51 } 52 int mid=(l+r)>>1; 53 build(rt<<1,l,mid); 54 build(rt<<1|1,mid+1,r); 55 up(rt); 56 } 57 void modify(int rt,int l,int r,int v) 58 { 59 if(l<=s[rt].l&&r>=s[rt].r) 60 { 61 s[rt].sum=(s[rt].sum+v*(s[rt].r-s[rt].l+1))%mod; 62 s[rt].tag=(s[rt].tag+v)%mod; 63 return ; 64 } 65 down(rt); 66 int mid=(s[rt].l+s[rt].r)>>1; 67 if(l<=mid) modify(rt<<1,l,r,v); 68 if(r>mid) modify(rt<<1|1,l,r,v); 69 up(rt); 70 } 71 int querry(int rt,int l,int r) 72 { 73 if(l<=s[rt].l&&r>=s[rt].r) 74 { 75 return s[rt].sum; 76 } 77 down(rt); 78 int ans=0; 79 int mid=(s[rt].r+s[rt].l)>>1; 80 if(l<=mid) ans=(ans+querry(rt<<1,l,r))%mod; 81 if(r>mid) ans=(ans+querry(rt<<1|1,l,r))%mod; 82 return ans; 83 } 84 //线段树 85 void dfs1(int x,int f,int deep) 86 { 87 dep[x]=deep; 88 fa[x]=f; 89 sz[x]=1; 90 int maxson=-1; 91 for(int i=head[x];i;i=e[i].nex) 92 { 93 int y=e[i].u; 94 if(y==f) continue; 95 dfs1(y,x,deep+1); 96 sz[x]+=sz[y]; 97 if(sz[y]>maxson){ 98 maxson=sz[y]; 99 son[x]=y; 100 } 101 } 102 } 103 void dfs2(int x,int tt) 104 { 105 id[x]=++num; 106 a[num]=wt[x]; 107 top[x]=tt; 108 if(!son[x]) return; 109 dfs2(son[x],tt); 110 for(int i=head[x];i;i=e[i].nex) 111 { 112 int y=e[i].u; 113 if(y==fa[x]||y==son[x]) continue; 114 dfs2(y,y); 115 } 116 } 117 int q1(int x,int y) 118 { 119 int ans=0; 120 while(top[x]!=top[y]) 121 { 122 if(dep[top[x]]<dep[top[y]]) swap(x,y); 123 ans+=querry(1,id[top[x]],id[x]); 124 ans%=mod; 125 x=fa[top[x]]; 126 } 127 if(dep[x]<dep[y]) swap(x,y); 128 ans+=querry(1,id[y],id[x]); 129 return ans%mod; 130 } 131 void tree_add(int x,int y,int v) 132 { 133 while(top[x]!=top[y]) 134 { 135 if(dep[top[x]]<dep[top[y]]) swap(x,y); 136 modify(1,id[top[x]],id[x],v%mod); 137 x=fa[top[x]]; 138 } 139 if(dep[x]<dep[y]) swap(x,y); 140 modify(1,id[y],id[x],v); 141 } 142 int son_add(int x,int v) 143 { 144 modify(1,id[x],id[x]+sz[x]-1,v%mod); 145 } 146 int son_querry(int x) 147 { 148 return querry(1,id[x],id[x]+sz[x]-1); 149 } 150 int main() 151 { 152 scanf("%d%d%d%d",&n,&m,&g,&mod); 153 for(int i=1;i<=n;i++) scanf("%d",&wt[i]); 154 for(int i=1;i<=n-1;i++) 155 { 156 int a,b; 157 scanf("%d%d",&a,&b); 158 add(a,b); 159 add(b,a); 160 } 161 dfs1(g,0,1); 162 dfs2(g,g); 163 build(1,1,n); 164 while(m--) 165 { 166 int aa,bb,cc,dd; 167 scanf("%d",&aa); 168 if(aa==1) 169 { 170 scanf("%d%d%d",&bb,&cc,&dd); 171 dd=dd%mod; 172 tree_add(bb,cc,dd); 173 } 174 else if(aa==2) 175 { 176 scanf("%d%d",&bb,&cc); 177 dd=q1(bb,cc); 178 printf("%d\n",dd); 179 } 180 else if(aa==3) 181 { 182 scanf("%d%d",&bb,&cc); 183 son_add(bb,cc); 184 } 185 else 186 { 187 scanf("%d",&bb); 188 cc=son_querry(bb); 189 printf("%d\n",cc); 190 } 191 } 192 return 0; 193 }