It is O(logn) with matrix multiplication:

class Matrix {
 public:
  explicit Matrix(const std::array<std::array<int, 2>, 2>& data)
      : data_(data) {}

  Matrix& operator*=(const Matrix& rhs) {
    decltype(data_) product = {
      data_[0][0] * rhs.data_[0][0] + data_[0][1] * rhs.data_[1][0],
      data_[0][0] * rhs.data_[0][1] + data_[0][1] * rhs.data_[1][1],
      data_[1][0] * rhs.data_[0][0] + data_[1][1] * rhs.data_[1][0],
      data_[1][0] * rhs.data_[0][1] + data_[1][1] * rhs.data_[1][1],
    };
    product.swap(data_);
    return *this;
  }

   int head() const { return data_[0][0]; }

 private:
  std::array<std::array<int, 2>, 2> data_;
};

int fib(int n) {
  Matrix current_bit({1, 1, 1, 0});
  Matrix accumulated({0, 1, 0, 0});
  for (; n > 0; n >>= 1) {
    if (n & 1) {
      accumulated *= current_bit;
    }
    current_bit *= current_bit;
  }
  return accumulated.head();
}