（详细揭秘）怎么把优选法改造为整数三分？

· · 算法·理论

问题：给定函数 G 与区间 [l,r]，保证 G 在 [l,r] 中是单峰且无平台的。怎么找到 G 在 [l,r] 上的最大值？

我们知道黄金三分（也称优选法）只需要求 G 在 \log_{\varphi}(r-l)（其中 \varphi=\frac{1+\sqrt{5}}{2}）个单点上的值，相比普通三分的 2\log_{2}(r-l) 优不少。但它要求 G 的定义域为实数域，能不能改造成整数上的？

考虑 \varphi 在整数上的代替物，容易想到斐波那契数列 F_n。我们便提出下面的算法流程：

  1. 找到最小的 k 使得 F_k\ge r-l，设 m_0=l+F_{k-2}，m_1=l+F_{k-1}。
  2. 比较 G(m_0) 与 G(m_1)：
    1. 若 G(m_0)>G(m_1)，则说明 (m_1,r] 内的点值不可能成为极值，我们将 r 移动到 m_1。此时 r-l=F_{k-1}，因此 k 需要减一，随后我们发现 m_1'=m_0 故点值可以复用，只需要重新计算 m_0' 处的点值。
    2. 若 G(m_0)\le G(m_1)，则说明 [l,m_0) 内的点值不可能成为极值，我们将 l 移动到 m_0。此时只有 F_{k-3}<r-l\le F_{k-1}，我们还要讨论它和 F_{k-2} 的大小关系。
      1. 若 r-l\le F_{k-2}，则 k 需要减二，m_1'=m_1 故点值可以复用，只需要重新计算 G(m_0')；
      2. 若 r-l>F_{k-2}，则 k 只需要减一，m_0'=m_1 故点值可以复用，只需要重新计算 G(m_1')。

再处理一些 corner case 就好了，显然每次迭代都会使得 k 至少减一，故迭代次数不超过 k=\log_\varphi (r-l)+O(1) 次，且每次迭代至多计算一个位置的点值，故 G 的计算次数也不超过 \log_{\varphi}(r-l)+O(1) 次。

实现的好像有点丑，有没有大手子写一份漂亮一点的。

struct fib_search {
  using u64 = unsigned long long;

  static constexpr int kL = 93;

  u64 f[kL];

  constexpr fib_search() {
    f[0] = f[1] = 1;
    for (int i = 2; i < kL; ++i) {
      f[i] = f[i - 1] + f[i - 2];
    }
  }
  template <typename U, typename T>
  auto find_max(U l, U r, T g) const {
    if (r - l <= 2) {
      auto ans = make_pair(g(l), l);
      for (U i = l + 1; i <= r; ++i) {
        ans = max(ans, make_pair(g(i), i));
      }
      return ans;
    }
    int k = lower_bound(f, f + kL, r - l) - f;
    U m0 = l + f[k - 2], m1 = l + f[k - 1];
    for (auto v0 = g(m0), v1 = g(m1);;) {
      if (v0 > v1) {
        r = m1;
        if (r - l <= 2) {
          return max(make_pair(g(l), l), make_pair(v0, m0));
        }
        m1 = m0, v1 = v0, --k, v0 = g(m0 = l + f[k - 2]);
      } else {
        l = m0;
        if (r - l <= 2) {
          return max(make_pair(g(r), r), make_pair(v1, m1));
        }
        if (r - l <= f[k - 2]) {
          k -= 2, v0 = g(m0 = l + f[k - 2]);
        } else {
          m0 = m1, v0 = v1, --k, v1 = g(m1 = l + f[k - 1]);
        }
      }
    }
  }
};
constexpr fib_search fib;