线段树（区间修改，区间和）：
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int c[1000000],n,m;
char s; void update(int p,int l,int r,int x,int add)
{
int m=(l+r) / 2;
if (l==r)
{
c[p]+=add;
return;
}
if (x<=m) update(p*2,l,m,x,add);
if (x>m) update(p*2+1,m+1,r,x,add);
c[p]=c[p<<1]+c[p<<1|1];
} int find(int p,int l,int r,int a,int b)
{
if (l==a && r==b) return c[p];
else
{
int m=(l+r) / 2;
if (b<=m) return find(p*2,l,m,a,b);
else if (a>m) return find(p*2+1,m+1,r,a,b);
else return find(p*2,l,m,a,m)+find(p*2+1,m+1,r,m+1,b);
}
} int main()
{
scanf("%d",&n);
scanf("%d",&m);
for (int i=1;i<=m;i++)
{
cin>>s;
if (s=='M')
{
int x,y;
scanf("%d%d",&x,&y);
update(1,1,n,x,y);
}
if (s=='C')
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",find(1,1,n,x,y));
}
}
}
线段树（lazy）：
线段树，并且单纯的线段树会超时，因为在将a到b的点全部加上c时，步骤太多，会超时。
需要优化。即lazy算法；
Lazy：
在将a~b点全部加c时，不要加到每个点，在表示区间的root结构体上增加一个inc域，将要加的值赋给这个inc域，然后就不要再往下了。
在求区间和时，将root中的inc值赋给要求的区间，并且将该节点的root置零。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#define ll long long
using namespace std;
ll a[1000005],t[5000005],n,lazy[5000005],m; ll read()
{
ll s=0;
char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9')
{
s=(s << 1) + (s << 3) +ch-'0';ch=getchar();
}
return s;
} void build(ll p,ll l,ll r)
{
if (l==r)
{
t[p]=a[l];
return;
}
ll m=(l+r)>>1;
build(p<<1,l,m);
build(p<<1|1,m+1,r);
t[p]=t[p<<1]+t[p<<1|1];
} void pushdown(ll x,ll len)
{
if (lazy[x]!=0)
{
lazy[x<<1]+=lazy[x];
lazy[x<<1|1]+=lazy[x];
t[x<<1]+=(len-len/2)*lazy[x];
t[x<<1|1]+=(len/2)*lazy[x];
lazy[x]=0;
}
} void update(ll a,ll b,ll l,ll r,ll x,ll p)
{
if (a<=l && b>=r)
{
t[p]+=(r-l+1)*x;
lazy[p]+=x;
return;
}
if (lazy[p]!=0) pushdown(p,r-l+1);
ll m=(l+r)/2;
if (b<=m) update(a,b,l,m,x,p<<1);
else if (a>m) update(a,b,m+1,r,x,p<<1|1);
else update(a,m,l,m,x,p<<1),update(m+1,b,m+1,r,x,p<<1|1);
t[p]=t[p<<1]+t[p<<1|1];
} ll find(ll a,ll b,ll l,ll r,ll p)
{
if (lazy[p]!=0) pushdown(p,r-l+1);
if (a==l && b==r) return t[p];
ll m=(l+r)/2;
if (b<=m) return find(a,b,l,m,p<<1);
else if (a>m) return find(a,b,m+1,r,p<<1|1);
else return find(a,m,l,m,p<<1)+find(m+1,b,m+1,r,p<<1|1);
} int main()
{
n=read(); m=read();
for (int i=1;i<=n;i++)
a[i]=read();
build(1,1,n);
int x,y,z;
for (int i=1;i<=m;i++)
{
x=read();
if (x==1)
{
x=read(),y=read(),z=read();
update(x,y,1,n,z,1);
}
else if (x==2)
{
y=read(),z=read();
printf("%lld\n",find(y,z,1,n,1));
}
}
}
二分图匹配：
#include <iostream>
#include <cstring>
#include <cstdio>
#define inf 1000007
using namespace std;
struct arr
{
int y, n;
}f[1000005];
int ls[1000005], n, m, tot, e, ans, link[1000005];
bool b[1000005]; void add(int x, int y)
{
f[++tot].y = y;
f[tot].n = ls[x];
ls[x] = tot;
} bool find(int x)
{
for (int i = ls[x]; i; i = f[i].n)
if (!b[f[i].y])
{
b[f[i].y] = 1;
if (!link[f[i].y] || find(link[f[i].y]))
{
link[f[i].y] = x;
return true;
}
}
return false;
} void work()
{
for (int i = 1; i <= n; i++)
{
memset(b, 0, sizeof(b));
if (find(i)) ans++;
}
} int main()
{
int x, y;
scanf("%d%d%d", &n, &m, &e);
for (int i = 1; i <= e; i++)
{
scanf("%d%d", &x, &y);
if (y > m) continue;
add(x, y);
}
work();
printf("%d", ans);
}
最小生成树：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
struct arr
{
int x,y,w;
}f[200007];
int g[5007],tot,n,m;
bool b[5007]; int cmp(arr a,arr b)
{
return a.w<b.w;
} int find(int x)
{
if (g[x]==x) return x;
g[x]=find(g[x]);
return g[x];
} int main()
{
cin>>n>>m;
int q,p,o,e=0;
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&q,&p,&o);
e++;
f[e].x=q;
f[e].y=p;
f[e].w=o;
}
sort(f+1,f+e+1,cmp);
for (int i=1;i<=n;i++)
g[i]=i;
int k=0;
for (int i=1;i<=e;i++)
{
if (k==n-1) break;
if (find(g[f[i].x])!=find(g[f[i].y]))
{
k++;
tot+=f[i].w;
g[find(f[i].x)]=find(f[i].y);
}
}
if (k==n-1) printf("%d",tot);
else printf("orz");
}
最短路（spfa）：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct arr
{
int to,next,w;
}f[5000007];
int n,m,s,d[1000007],ls[1000007],str[1000007];
bool b[1000007]; void spfa()
{
for (int i=1;i<=n;i++)
d[i]=2147483647;
d[s]=0;
int head=0,tail=1;
b[s]=1;
str[1]=s;
while (head<tail)
{
head++;
int t=ls[str[head]];
while (t>0)
{
if (d[f[t].to]>d[str[head]]+f[t].w)
{
d[f[t].to]=d[str[head]]+f[t].w;
if (!b[f[t].to])
{
b[f[t].to]=1;
tail++;
str[tail]=f[t].to;
}
}
t=f[t].next;
}
b[str[head]]=0;
}
} int main()
{
scanf("%d%d%d",&n,&m,&s);
int p,q;
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&q,&p,&f[i].w);
f[i].to=p;
f[i].next=ls[q];
ls[q]=i;
} spfa();
for (int i=1;i<=n;i++)
printf("%d ",d[i]);
}
并查集
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n,m,f[10007]; int find(int x)
{
if (f[x]==x) return x;
f[x]=find(f[x]);
return f[x];
} int main()
{
scanf("%d%d",&n,&m);
int q,p,z;
for (int i=1;i<=n;i++)
f[i]=i;
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&z,&q,&p);
if (z==1)
{
f[find(q)]=find(p);
}
if (z==2)
{
if (find(q)==find(p)) cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
}
}
KMP
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int a[1000005],b[1000005],p[1000005],n,m,next[1000005],ans;
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &p[i]);
a[i - 1] = p[i] - p[i - 1];
}
for (int i = 1; i <= m; i++)
{
scanf("%d", &p[i]);
b[i - 1] = p[i] - p[i - 1];
}
int j = 0;
for (int i = 2; i < m; i++)
{
while (j > 0 && b[j + 1] != b[i]) j = next[j];
if (b[j + 1] == b[i]) j += 1;
next[i] = j;
}
j = 0;
for (int i = 1; i < n; i++)
{
while (j > 0 && b[j + 1] != a[i]) j = next[j];
if (b[j + 1] == a[i]) j += 1;
if (j == m - 1)
{
ans++;
j = next[j];
}
}
printf("%d", ans);
}
快速幂
int pow4(int a,int b)
{
int r=1,base=a;
while(b)
{
if(b&1) r*=base;
base*=base;
b>>=1;
}
return r;
}
强连通分量（tarjan）：
#include <cstdio>
#include <iostream>
using namespace std;
struct arr
{
int x,y,next;
};
arr f[3000];
int ls[40000],stack[40000],belong[40000],low[40000],dfn[40000],cnt,e,n,d,tot,rd[40000],cd[40000],ans,s1,s2;
bool ins[40000]; void add(int x,int y)
{
e++;
f[e].x=x;
f[e].y=y;
f[e].next=ls[x];
ls[x]=e;
} void tarjan(int i)
{
int t=0;
int j=0;
d++;
dfn[i]=d;
low[i]=d;
tot++;
stack[tot]=i;
t=ls[i];
ins[i]=1;
while (t>0)
{
j=f[t].y;
if (dfn[j]==0)
{
tarjan(j);
if (low[i]>low[j]) low[i]=low[j];
}
else if (ins[j]&&dfn[j]<low[i]) low[i]=dfn[j];
t=f[t].next;
}
if (dfn[i]==low[i])
{
cnt++;
do
{
j=stack[tot];
ins[j]=false;
tot--;
belong[j]=cnt;
}
while (i!=j);
} } int main()
{
cin>>n;
int j;
e=0;
for (int i=1;i<=n;i++)
{
while (scanf("%d",&j)&&j!=0)
add(i,j);
}
for (int i=1;i<=n;i++)
if (dfn[i]==0) tarjan(i);
for (int i=1;i<=e;i++)
if (belong[f[i].x]!=belong[f[i].y])
{
cd[belong[f[i].x]]++;
rd[belong[f[i].y]]++;
}
ans=0;
s1=0;
s2=0;
for (int i=1;i<=cnt;i++)
{
if (rd[i]==0) {ans++; s1++;}
if (cd[i]==0) s2++;
}
cout<<ans<<endl;
if (cnt==1) {s1=0; s2=0;}
if (s1>s2) cout<<s1<<endl;
else cout<<s2<<endl;
}
最短路（floyd）：
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && i != k && j != k)
f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
最近公共祖先（lca）：
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
struct arr {int x,y,n;}f[60007];
int ls[30007],n,m,e,deep[30007],fa[30007][30],ans; void add(int x, int y)
{
f[++e].x = x;
f[e].y = y;
f[e].n = ls[x];
ls[x] = e;
} void dfs(int x, int la)
{
deep[x] = deep[la] + 1;
fa[x][0] = la;
for (int i = ls[x]; i ; i = f[i].n)
{
if (f[i].y != la)
{
dfs(f[i].y, x);
}
}
} int lca(int q, int p)
{
if (deep[p] < deep[q]) swap(p,q);
for (int j = 20; j >= 0; j--)
if (deep[fa[p][j]] >= deep[q])
p = fa[p][j];
if (p == q) return p;
for (int j = 20; j >= 0; j--)
if (fa[p][j] != fa[q][j])
{
p = fa[p][j], q = fa[q][j];
}
return fa[p][0];
} int main()
{
scanf("%d", &n);
int x, y;
for (int i = 1; i <= n - 1; i++)
{
scanf("%d%d", &x, &y);
add(x, y);
add(y, x);
}
dfs(1, 0);
for (int j = 1; j <= 20; j++)
for (int i = 1; i <= n; i++)
fa[i][j] = fa[fa[i][j - 1]][j - 1];
scanf("%d", &m);
scanf("%d", &x);
m--;
while (m--)
{
scanf("%d", &y);
ans += deep[x] + deep[y] - deep[lca(x, y)] * 2;
x = y;
}
printf("%d", ans);
}