跳转至

倍增

本頁面將簡要介紹倍增法。

定義

倍增法（英語：binary lifting），顧名思義就是翻倍。它能夠使線性的處理轉化為對數級的處理，大大地優化時間複雜度。

這個方法在很多算法中均有應用，其中最常用的是 RMQ 問題和求 LCA（最近公共祖先）。

應用

RMQ 問題

參見：RMQ 專題

RMQ 是 Range Maximum/Minimum Query 的縮寫，表示區間最大（最小）值。使用倍增思想解決 RMQ 問題的方法是 ST 表。

樹上倍增求 LCA

參見：最近公共祖先

例題

題 1

例題

如何用盡可能少的砝碼稱量出 \([0,31]\) 之間的所有重量？（只能在天平的一端放砝碼）

解題思路

答案是使用 1 2 4 8 16 這五個砝碼，可以稱量出 \([0,31]\) 之間的所有重量。同樣，如果要稱量 \([0,127]\) 之間的所有重量，可以使用 1 2 4 8 16 32 64 這七個砝碼。每次我們都選擇 2 的整次冪作砝碼的重量，就可以使用極少的砝碼個數量出任意我們所需要的重量。

為什麼説是極少呢？因為如果我們要量出 \([0,1023]\) 之間的所有重量，只需要 10 個砝碼，需要量出 \([0,1048575]\) 之間的所有重量，只需要 20 個。如果我們的目標重量翻倍，砝碼個數只需要增加 1。這叫「對數級」的增長速度，因為砝碼的所需個數與目標重量的範圍的對數成正比。

題 2

例題

給出一個長度為 \(n\) 的環和一個常數 \(k\)，每次會從第 \(i\) 個點跳到第 \((i+k)\bmod n+1\) 個點，總共跳了 \(m\) 次。每個點都有一個權值，記為 \(a_i\)，求 \(m\) 次跳躍的起點的權值之和對 \(10^9+7\) 取模的結果。

數據範圍：\(1\leq n\leq 10^6\)，\(1\leq m\leq 10^{18}\)，\(1\leq k\leq n\)，\(0\le a_i\le 10^9\)。

解題思路

這裏顯然不能暴力模擬跳 \(m\) 次。因為 \(m\) 最大可到 \(10^{18}\) 級別，如果暴力模擬的話，時間承受不住。

所以就需要進行一些預處理，提前整合一些信息，以便於在查詢的時候更快得出結果。如果記錄下來每一個可能的跳躍次數的結果的話，不論是時間還是空間都難以承受。

那麼應該如何預處理呢？看看第一道例題。有思路了嗎？

回到本題。我們要預處理一些信息，然後用預處理的信息儘量快的整合出答案。同時預處理的信息也不能太多。所以可以預處理出以 2 的整次冪為單位的信息，這樣的話在預處理的時候只需要處理少量信息，在整合的時候也不需要大費周章。

在這題上，就是我們預處理出從每個點開始跳 1、2、4、8 等等步之後的結果（所處點和點權和），然後如果要跳 13 步，只需要跳 1+4+8 步就好了。也就是説先在起始點跳 1 步，然後再在跳了之後的終點跳 4 步，再接着跳 8 步，同時統計一下預先處理好的點權和，就可以知道跳 13 步的點權和了。

對於每一個點開始的 \(2^i\) 步，記錄一個 go[i][x] 表示第 \(x\) 個點跳 \(2^i\) 步之後的終點，而 sum[i][x] 表示第 \(x\) 個點跳 \(2^i\) 步之後能獲得的點權和。預處理的時候，開兩重循環，對於跳 \(2^i\) 步的信息，我們可以看作是先跳了 \(2^{i-1}\) 步，再跳 \(2^{i-1}\) 步，因為顯然有 \(2^{i-1}+2^{i-1}=2^i\)。即我們有 sum[i][x] = sum[i-1][x]+sum[i-1][go[i-1][x]]，且 go[i][x] = go[i-1][go[i-1][x]]。

當然還有一些實現細節需要注意。為了保證統計的時候不重不漏，我們一般預處理出「左閉右開」的點權和。亦即，對於跳 1 步的情況，我們只記錄該點的點權和；對於跳 2 步的情況，我們只記錄該點及其下一個點的點權和。相當於總是不將終點的點權和計入 sum。這樣在預處理的時候，只需要將兩部分的點權和直接相加就可以了，不需要擔心第一段的終點和第二段的起點會被重複計算。

這題的 \(m\leq 10^{18}\)，雖然看似恐怖，但是實際上只需要預處理出 \(65\) 以內的 \(i\)，就可以輕鬆解決，比起暴力枚舉快了很多。用行話講，這個做法的 時間複雜度 是預處理 \(\Theta(n\log m)\)，查詢每次 \(\Theta(\log m)\)。

參考代碼 
 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
#include <cstdio>
using namespace std;

const int mod = 1000000007;

int modadd(int a, int b) {
  if (a + b >= mod) return a + b - mod;  // 減法代替取模，加快運算
  return a + b;
}

int vi[1000005];

int go[75][1000005];  // 將數組稍微開大以避免越界，小的一維儘量定義在前面
int sum[75][1000005];

int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", vi + i);
  }

  for (int i = 1; i <= n; ++i) {
    go[0][i] = (i + k) % n + 1;
    sum[0][i] = vi[i];
  }

  int logn = 31 - __builtin_clz(n);  // 一個快捷的取對數的方法
  for (int i = 1; i <= logn; ++i) {
    for (int j = 1; j <= n; ++j) {
      go[i][j] = go[i - 1][go[i - 1][j]];
      sum[i][j] = modadd(sum[i - 1][j], sum[i - 1][go[i - 1][j]]);
    }
  }

  long long m;
  scanf("%lld", &m);

  int ans = 0;
  int curx = 1;
  for (int i = 0; m; ++i) {
    if (m & (1ll << i)) {  // 參見位運算的相關內容，意為 m 的第 i 位是否為 1
      ans = modadd(ans, sum[i][curx]);
      curx = go[i][curx];
      m ^= 1ll << i;  // 將第 i 位置零
    }
  }

  printf("%d\n", ans);
}
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, ShadowsEpic, Fomalhauthmj, siger-young, MingqiHuang, Xeonacid, hsfzLZH1, orzAtalod, NachtgeistW
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用