堆的话是之前就学过的东西,也写过博客,可以带过:
2.LCA:
基本用途:求树上最短路
求LCA的朴素算法:
首先处理深度;
然后:
复杂度O(deep(tree))
对于随机构造的树,可能这种算法还可以;但是当数据别出心裁构造的伐,如果退化成一条链,显然就凉凉了~;
所以我们考虑优化:
既然一个个跳不行,我们可不可以一次跳多个?
显然可以!
但是如果单纯的枚举一次跳多少个的伐,当数据够大时,我们枚举的范围可能是上百万的,也不够优;
想到,任何一个数都可以表示为二进制,也就表示每个数都可以拆成若干个2的乘方相加;
令p[x][i]表示x的2^i的祖先是谁,那么我们可以知道p[x][0]表示x的父亲,通过此可以想到递推方程:p[x][i]=p[p[x][i-1]][i-1];x的2^i祖先,等于x的2^(i-1)的祖先的2^(i-1)的祖先:
基本流程与上面相同,但是我们不再是一个一个的往上跳。从乘方最大的的开始枚举,如果跳上去以后父亲不同就往上跳,父亲相同不跳:
A和B的祖先开始是不一样的,从LCA开始,以上都一样,但是我们无法确定LCA,但是我们可以确定最后一个不一样的;
伪代码:
fori=16~0if(p[A][i]!=p[B][i])A=p[A][i];B=p[B][i];LCA一般用于解决一类可差分的问题,比如求AB之间的最短路径:求出A到根的路径,B到根的路径,减去两倍根到LCA的路径;
3.ST表:
用于求解没有修改的区间最大值问题
mx[i][j]表示从i~i+2j-1的最大值
求一个区间[l,r]的最大值,可以拆分为两部分:
首先一个区间[l,r],求出区间长度:k=l-r;
然后我们记录p=log2k;
求这个区间的最大值,即为:max(mx[l][p],mx[r-2p+1][p]);
关于mx数组的求法:递推:mx[i][j]=max(mx[i][j-1],mx[i+2j-1][j-1]);
举个栗子:
[19,46]
k=46-19=28;p=16;ans=max(mx[19][4],mx[31][4])//可能写炸了将就着;
4.Hash:
Hash(字符串)=>int
Hash将一个字符串转换为一个int;
Hash是允许冲突的,但是我们要尽量避免冲突;
设计Hash:
1.随便取一个p,把字符串当做p进制数(建议取质数,并且是大于字符串大小的质数)
2.取字符的ASCII码*p^i(i表示此字符在此字符串中是第几位[fromrighttoleft]),然后计算一段字符串的每个字符,把值相加,就是这一段字符串的Hash值;
3.显然你看这个数会很大,可能会炸。我们可以取一个大质数mod用来取模,当然也可以用Unsignedlonglong强势自然溢出;
具体的处理:
求字符串,每个前缀的哈希值;
Hi:1~i的Hash值;
Hi=Hi-1*p+Si
Hash(i,j)=Hj-Hi*pj-i+1
5.并查集:
令fa[x]表示x的父亲;树根的父亲等于本身;
查询A和B在不在一个集合中:找到A和B的根,比较是否相同;
如何将两个集合合并:
找A代表元AA,B代表元BB,令fa[AA]=BB;
路径压缩:直接指向代表元
6.树状数组:
支持单点修改,区间查询;其实也可以区间修改,单点查询(利用差分)
所求所有问题,必须存在逆元?
主要应用:
1.线段树常数过大时
2.线段树功能过多时
然后只讲代码实现,具体原理↑:
短短几行代码:
intlowbit(intx){returnx&(-x);}voidmodify(intx,inty){//addytoa[x]for(inti=x;i<=n;i+=lowbit(i))c[i]+=y;}intquery(intx){//sumofa[1]...a[x]intret=0;for(inti=x;i;i-=lowbit(i))ret+=c[i];returnret;}intquery(intl,intr){returnquery(r)-query(l-1);}7.线段树(抽象线段二叉树;):
支持区间修改,区间查询;
主要应用:一类区间修改区间查询的问题;
Sum线段树:
先是单点修改:
区间查询:
任何一条线段,都可以被logn条线段覆盖;
递归看关系;
从最大的开始看,然后有关系就继续往下递归直到被完全覆盖,返回,统计进答案;
线段树的节点个数2n级别的,*4防止溢出写炸;
前置:
structNode{intl,r;intsum;inttag;}t[N<<2];voidpushup(intrt){t[rt].sum=t[rt<<1].sum+t[rt<<1|1].sum;}建树:
voidbuild(intrt,intl,intr){t[rt].l=l;t[rt].r=r;if(l==r){t[rt].sum=a[l];return;}intmid=(l+r)>>1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);pushup(rt);}单点修改a[p]=c;
voidmodify(intrt,intp,intc){if(t[rt].l==t[rt].r){t[rt].sum=c;return;}pushdown(rt);intmid=(t[rt].l+t[rt].r)>>1;if(p<=mid)modify(rt<<1,p,c);elsemodify(rt<<1|1,p,c);pushup(rt);}区间查询:
intquery(intrt,intl,intr){if(l<=t[rt].l&&t[rt].r<=r){returnt[rt].sum;}pushdown(rt);intret=0;intmid=(t[rt].l+t[rt].r)>>1;if(l<=mid)ret+=query(rt<<1,l,r);if(mid 懒标记: 标记这一整段线段的每一个值,都加一个特定的数; 懒惰的:先放在哪里,在没有必要下方时,就不下放:标记下放:pushdown; Pushdown: 将此点的标记下放给左右儿子,然后自己的标记清0; 然后同时维护左右节点的区间和; 碰到这个节点就下放 voidadd(intrt,intl,intr,intc){if(l<=t[rt].l&&t[rt].r<=r){t[rt].tag+=c;t[rt].sum+=c*(t[rt].r-t[rt].l+1);return;}pushdown(rt);intmid=(t[rt].l+t[rt].r)>>1;if(l<=mid)add(rt<<1,l,r,c);if(mid