Not a data structure, and not really obscure, but I am still amazed by the concept of solving DP (dynamic-programming) problems in O(log N) instead of O(N) time

Not a data structure, and not really obscure, but I am still amazed by the concept of solving DP (dynamic-programming) problems in O(log N) instead of O(N) time by writing the solution as a Fast Matrix Exponentiation equation: https://www.geeksforgeeks.org/matrix-exponentiation/ https://www.geeksforgeeks.org/matrix-exponentiation/