Fibonacci Prefix Sum — Solution & Editorial

Back to the Problem

The identity ∑_i=0..N F(i) = F(N+2) − 1 collapses the sum to one Fibonacci value (matrix power).

Complexity: O(log N)