• 個人理解：按照翻倍的形式處理數據，使得加速某些詢問過程
• 具體應用：
  • 快速冪：O（log₂n）

    計算a^b的值，通常是枚舉b個a相乘，但若b很大時，則需要用到快速冪。

    舉一個栗子來說明快速冪的做法:

    若要求21⁶⁰的值，則把60看成二進制數111100，

    即我們要求得21^111100(2)的值，

    又因為基于a^b1×a^b2×a^b3×……a^bn = a^{b1+b2+b3+……+bn}

    所以21^111100(2)可以看成是21^000100(2)×21^001000(2)×21^010000(2)

    ??????????????????????????????????????????? ×21^100000(2)

    可以直接從低到高枚舉b（即60）的二進制數每一位，計算出這一位為1的二進制數對應的冪值，用倍增的思想，快速求出a的2^k次方：

    如a^1000(2)=a¹⁰⁰⁽²⁾×a¹⁰⁰⁽²⁾

    若b的該位為1，則把該冪值乘進答案。

    ?

  • 代碼:

    const int P=100007; int pow(int a,int b) //求a^b,對P取模 {int ans=1; a%=P;while (b){if (b&1) ans=1ll*ans*a%P;b>>=1;a=1ll*a*a%mo;}return ans; }

• • RMQ (Range Minimum/Maximum Query) 用倍增算法求ST表：

    預處理 O（n log₂ n） 查詢 O（1）

    舉個栗子：給出一個序列，多次詢問區間[ l , r ]中的最小值

    用st[i][j]，表示以i位置作為結尾，包含該位在內，前2^j個元素的最小值

    通過如下代碼，用倍增思想，遞推出ST表（包含詢問代碼)

    #include<iostream> using namespace std; int n,a,b; int st[10005][15]; int log2[10005]; void make_ST(){for(int j=1;(1<<j)<=n;j++)for(int i=(1<<j);i<=n;i++)st[i][j]=min(st[i][j-1],st[i-(1<<(j-1))][j-1]); } int query(int l,int r){int k=log2[r-l+1];return min(st[l+(1<<k)-1][k],st[r][k]); } int main() {scanf("%d",&n);log2[1]=0;;for(int i=2;i<=n;i++) log2[i]=log2[i>>1]+1;for(int i=1;i<=n;i++) scanf("%d",&st[i][0]);make_ST();while(scanf("%d%d",&a,&b)!=EOF) printf("%d\n",query(a,b));return 0; }

?

• • 樹上倍增法求LCA：預處理O（n log₂ n） 查詢 O（log₂ n）

    同樣的，用一個fa[i][j]表示從i節點向上走2^j個單位到哪個節點,代碼：

    void dfs(int u,int father){ //從根結點u開始dfs，u的父親是fad[u]=d[fa]+1; //u的深度為它父親的深度+1fa[u][0]=father; //u向上走2^0步到達的結點是其父親for(int i=1;(1<<i)<=d[u];i++) fa[u][i]=fa[fa[u][i-1]][i-1]; //預處理fa時，保證能從u走到fa[u][i]for(int i=head[u];i!=-1;i=e[i].next){//對于u的每個兒子 int v=e[i].v; if(v!=father)dfs(v,u);} //遞歸處理以v為根結點的子樹} } int lca(int a,int b) {if(d[a] > d[b]) swap(a , b) ; //保證a點在b點上面for(int j = 20 ; j >= 0 ; j--) //將b點向上移動到和a的同一深度if(d[a] <= d[b] - (1<<j)) b = fa[b][j] ;if(a == b) return a ; //如果a和b相遇for(int j = 20 ; j >= 0 ; j--){ //a,b同時向上移動if(fa[a][j] == fa[b][j]) continue ;//如果a,b的2^j祖先相同，則不移動a = fa[a][j] , b = fa[b][j] ;//否則同時移動到2^j處 }return fa[a][0] ; //返回最后a的父親結點 }

?

• • 倍增求ST表，RMQ求LCA：預處理O（n log₂ n） 查詢 O（1）

    把樹轉成序列，在序列中查詢兩點的lca

    對數進行dfs遍歷，遇到一個點（即使以前遇到過），就把它加入一個序列數組

    同時記錄下每個節點在序列中第一次出現的位置

    不難發現，對于詢問的兩個點（a,b且假設dfs時a比b先被遍歷），在dfs時，從a遍歷到b的過程中，一定會經過他們的LCA，即在遍歷序列中，它們的LCA一定被記錄在了這兩個點之間：

    舉個栗子：比如要求4號節點和8號節點的LCA，則可以發現在遍歷序列中，in[4]位置到in[8]位置之間，出現里一次它們的LCA：1 號節點

    那該如何找到它們的LCA呢。

    可以發現，在深度序列中，in[4]位置到in[8]位置之間，最小值（為1）對應的即是遍歷序列中的它們的LCA：1 號節點

    結論：兩個節點在深度序列中對應的區間的最小值即是它們的LCA的深度

    有了“區間最小值”這一東西，之前的ST表，RMQ就可以拿來用了

    /* stm[i][j]:在深度序列中，以i位置作為結尾，包含該位在內，前2^j個元素的最小值（最小深度） stu[i][j]:stm[i][j]記錄的最小值對應的節點 */ void dfs(int u,int fa,int dep){deep[u]=deep; stm[++cnt][0]=deep; stu[cnt][0]=u; in[u]=cnt;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v==fa) continue;dfs(v,u,deep+1);stm[++cnt][0]=deep; stu[cnt][0]=u;} } void make_ST(){for(int j=1;(1<<j)<=cnt;j++)for(int i=(1<<j);i<=cnt;i++)if(stm[i][j-1]<stm[i-(1<<(j-1))][j-1])stm[i][j]=stm[i][j-1],stu[i][j]=stu[i][j-1];else stm[i][j]=stm[i-(1<<(j-1))][j-1],stu[i][j]=stu[i-(1<<(j-1))][j-1]; }int dis(int x,int y){int l,r,k,lca;l=min(in[x],in[y]);r=max(in[x],in[y]);k=log2[r-l+1];if(stm[l+(1<<k)-1][k]<stm[r][k]) lca=stu[l+(1<<k)-1][k];else lca=stu[r][k]; }
  • 后綴數組倍增算法 O(n log₂n)

  • 突然想起，補上模板。

void build(int n,int m) {int *x=wa,*y=wy,i;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++) c[x[i]=s[i]]++;for(i=1;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;for(int k=1;k<=n;k<<=1){int p=0;for(i=n-k;i<n;i++) y[p++]=i;for(i=0;i<n;i++) if(sa[i]>=k) y[p++]=sa[i]-k;for(i=0;i<m;i++) c[i]=0;for(i=0;i<n;i++) c[x[y[i]]]++;for(i=1;i<m;i++) c[i]+=c[i-1];for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];m=1; swap(x,y); x[sa[0]]=0;for(i=1;i<n;i++)x[sa[i]]=cmp(y,i,k,n)?m-1:m++;if(m>=n) break;}for(i=0;i<n;i++) rank[sa[i]]=i;int h=0;for(i=0;i<n;i++){if(h) h--;if(rank[i]==0) continue;int j=sa[rank[i]-1];while(s[i+h]==s[j+h]) h++;height[rank[i]]=h;} }

?

• 某些用到倍增的題目?
  • NOIP 2012 開車旅行 codevs 1199
  • 暴力的話是O（n²+nm），由于決策單一（即某人從某點出發到下一點這一過程是唯一確定的），可以進行倍增加速。
  • 由于是兩人交替走，比一般的路徑倍增要麻煩一點
  • 先借助set預處理出兩個人分別從i號點向前走的下一個點是哪個以及走的距離。
  • 然后用to[i][j]表示從i號點出發，走2^j輪（一輪為小A先走，小B再走）到達的目的地。用dis[i][j][0/1]（0：小B，1：小A）與上面的to數組對應，即分別表示從i號點出發，走2^j輪，小B/小A走過的距離和。

    這樣通過倍增后，加速了答案的尋找過程，

    將時間復雜度優化為了O（n log₂n+m log₂n）

    更加詳細的大佬題解-------------------------------------------------------->

    代碼：

    #include<set> #include<cstdio> #include<cstring> #include<iostream> #define INF 0x3f3f3f3f #define eps 0.000003 #define MAXN 100005 #define siter set<info>::iterator #define info(a,b) (info){a,b} using namespace std;//0 小B 1 小A struct info{int h,p;bool operator <(const info rtm) const{return h<rtm.h;} }; int to[MAXN][25],dis[MAXN][25][2],des[MAXN][2],len[MAXN][2],ans[2]; int he[MAXN]; int n,m,x,st; set<info>s; int sign(double i){if(-eps<=i&&i<=eps) return 0;if(i<-eps) return -1;return 1; } int distant(int i,int j){return he[i]>he[j]?he[i]-he[j]:he[j]-he[i]; } void update(int i,info p){int j=p.p,d=distant(i,j);if(d<len[i][0]||(d==len[i][0]&&he[j]<he[des[i][0]])){len[i][1]=len[i][0];des[i][1]=des[i][0];len[i][0]=d;des[i][0]=j; }else if(d<len[i][1]||(d==len[i][1]&&he[j]<he[des[i][1]])){len[i][1]=d;des[i][1]=j;} } void drive(int i,int v){for(int j=20;j>=0;j--) if(dis[i][j][0]+dis[i][j][1]<=v&&to[i][j]){ans[0]+=dis[i][j][0];ans[1]+=dis[i][j][1];v=v-dis[i][j][0]-dis[i][j][1];i=to[i][j];}if(len[i][1]<=v&&des[i][1]) ans[1]+=len[i][1]; } int main() {scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&he[i]),len[i][0]=len[i][1]=INF;siter si;for(int i=n;i>=1;i--){s.insert(info(he[i],i));si=s.find(info(he[i],i));si++;if(si!=s.end()){update(i,*si);si++; if(si!=s.end()) update(i,*si); si--;}si--;if(si!=s.begin()){si--; update(i,*si);if(si!=s.begin()) si--,update(i,*si);}}for(int i=1;i<=n;i++) to[i][0]=des[des[i][1]][0],dis[i][0][1]=len[i][1],dis[i][0][0]=len[des[i][1]][0];for(int j=1;j<=20;j++)for(int i=1;i<=n;i++)to[i][j]=to[to[i][j-1]][j-1],dis[i][j][0]=dis[i][j-1][0]+dis[to[i][j-1]][j-1][0],dis[i][j][1]=dis[i][j-1][1]+dis[to[i][j-1]][j-1][1];scanf("%d",&x);double rat=1e9; int ap=0;for(int i=1;i<=n;i++){ans[0]=ans[1]=0;drive(i,x);double tmp=ans[0]? 1.0*ans[1]/ans[0]:1e9;if(sign(rat-tmp)==0&&he[i]>he[ap]) ap=i;if(sign(rat-tmp)>0) ap=i,rat=tmp;}printf("%d\n",ap);scanf("%d",&m);for(int i=1;i<=m;i++){ans[0]=ans[1]=0;scanf("%d%d",&st,&x);drive(st,x);printf("%d %d\n",ans[1],ans[0]);}return 0; }

• • NOIP 2012 疫情控制 洛谷 1084

  • 貪心+二分+倍增

  • 二分時間，check操作，將所有軍隊按能否到達根節點分成兩類

    A類：無法在二分的時間內達到根節點。

    根據貪心策略，將這些軍隊移動到盡可能靠上的位置一定更優，所以把他們移動到他們所能到達的最靠近根的位置

    B類：在二分的時間內可以到達根節點。

    把他們放入一個數組，按到達根節點后剩余的時間從小到大排序。

    再對樹跑一個dfs，維護出根的哪些兒子節點還需要一個B類軍隊去駐扎，把這些兒子節點放入另一個數組，按到根的時間從小到大排序。

    進行貪心，嘗試用B類軍隊去覆蓋沒有還需要被駐扎的（根的兒子）節點：

    對于從小到大枚舉到的某一個B類軍隊，首先判斷他到根節點時進過的那個根的兒子節點是否被駐扎，若沒有，則直接去駐扎那個節點。若已被駐扎，則嘗試去駐扎從小到大枚舉到的還需要被駐扎的第一個節點。（有一點繞，好好理解一下，正確性很容易證明）

    最后判斷該時間下，那些還需要被駐扎的（根的兒子）節點是否被駐扎完。

    至于倍增用在哪里，顯而易見，在將軍隊向上移動時，不可能一個一個地向father移動，所以倍增一下，加速移動過程。

    代碼：

    洛谷和Vijos上過了，但Codevs和Tyvj上卻WA了一個點，在Tyvj上把數據下了下來，手測卻發現輸出是正確的……

    不明原因，非常絕望，望有心人能解答疑難。

    #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long #define MAXN 50005 using namespace std; struct edge{int to,next;ll val; }e[MAXN*2]; struct node{int id; ll val;bool operator<(const node &rtm) const{return val<rtm.val;} }ar[MAXN],ne[MAXN]; ll stt[MAXN][20]; int stu[MAXN][20]; int p[MAXN],from[MAXN],head[MAXN]; bool vis[MAXN]; ll l,r,mid,ans; int n,m,ent=1,rs,cnt,nnt; void add(int u,int v,int w){e[ent]=(edge){v,head[u],1ll*w};head[u]=ent++; } void dfs(int u,int fa,ll dis,int fr){if(fa==1) rs++;stu[u][0]=fa;stt[u][0]=dis;if(fa==1) from[u]=u;else from[u]=fr;for(int j=1;j<=16;j++){stu[u][j]=stu[stu[u][j-1]][j-1];stt[u][j]=stt[u][j-1]+stt[stu[u][j-1]][j-1];}for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v==fa) continue;if(u==1) dfs(v,u,e[i].val,v);else dfs(v,u,e[i].val,fr);} } void update(int u,int fa){bool fg=1,fl=0;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(v==fa) continue;fl=1;update(v,u);if(!vis[v]) fg=0;if(u==1&&!vis[v]) ne[++nnt]=(node){v,e[i].val};}if(fl) vis[u]=fg|vis[u]; } bool check(ll x){ll tmp;int u;cnt=0; nnt=0;memset(vis,0,sizeof(vis));vis[0]=1;for(int i=1;i<=m;i++){tmp=x; u=p[i];for(int j=16;j>=0;j--)if(stu[u][j]&&tmp>=stt[u][j]){tmp-=stt[u][j];u=stu[u][j];}if(u==1) ar[++cnt]=(node){p[i],tmp};else vis[u]=1;}update(1,0);sort(ne+1,ne+nnt+1);sort(ar+1,ar+cnt+1);int pp=1,res=nnt;for(int i=1;i<=cnt;i++){while(vis[ne[pp].id]) pp++;if(!vis[from[ar[i].id]]){vis[from[ar[i].id]]=1;res--;}else{if(ar[i].val>=ne[pp].val){vis[ne[pp].id]=1;res--;}}if(!res) return 1;}return 0; } void Binary(){while(l<=r){mid=(l+r)/2;if(check(mid)) ans=mid,r=mid-1;else l=mid+1;}printf("%lld",ans); } int main() {scanf("%d",&n);l=1; r=0;for(int i=1,a,b,c;i<n;i++){scanf("%d%d%d",&a,&b,&c);add(a,b,c); add(b,a,c);r+=1ll*c;}dfs(1,0,0,0);scanf("%d",&m);for(int i=1;i<=m;i++)scanf("%d",&p[i]);if(m<rs) printf("-1\n");else Binary();return 0; }

• 總結：

  由NOIP2012的兩道題來看（一年考的兩個題都涉及到倍增，而且代碼都這么惡心……），倍增多半不會直接考，而是在解題時需要用到上文中的某幾個應用來優化，或者說是加速某些答案（或者中間答案）的尋找過程。

  倍增是一種十分常用且實用的技巧，特別是那幾個應用，一定要掌握到位。

轉載于:https://www.cnblogs.com/zj75211/p/7568880.html

總結

以上是生活随笔為你收集整理的●(考试失误导致的)倍增总结的全部內容，希望文章能夠幫你解決所遇到的問題。

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