成倍增长数值

例子

比如在一个 N 非常大的数组里，快速找到区间中 倍增法 - 图1 中最大的数值。比较容易想到用一个 倍增法 - 图2 数组来维护“比 i 更大的最近的数“的坐标，依次 next 找到最大的值。但是在最差情况下，这样还是很慢。

观察到通过两次next得到 倍增法 - 图3，而 倍增法 - 图4 ，这样成倍增长，就能很快逼近目标，使用时从最大的数值 倍增法 - 图5 开始找

  1.              8  7  6  5  4  3  2  1
  2. next   1  2  3  4  5  6  7 -1 
  3. next2  2  3  4  5  6  7 -1 -1
  4. next4  4  5  6  7 -1 -1 -1 -1
  5. next8 -1 -1 -1 -1 -1 -1 -1 -1

那么要找8后面最小的数的话，先查询 next8[0] 发现是 -1，然后查询 next4[0] 发现有 4，然后查询 next2[4]，发现有 6，然后查询 next[6] 发现有 7 结束。
平均查询 倍增法 - 图6 次

实战