Laser beam scanning technology has potential applications in various fields, including LIDAR, laser processing, and optical communication. However, the capability of non-mechanical beam scanning is limited by the response time of an optical element, posing challenges in achieving both high-speed scanning and reconfigurable output beams. Here we propose a new concept, to the best of our knowledge, of the frequency-encoded optical phased array (OPA) to enable high-speed reconfigurable dynamic scanning. This is achieved by employing the customized frequency deviations on the array elements of the OPA. It is turned out that, in this way, the dynamic spatiotemporal beams with continuous scanning capability can be realized. We further find that the scanning speed is linearly proportional to the frequency deviation. Moreover, we are able to give access to multi-directional and customizable structured spatiotemporal beam scanning by encoding the on-demand frequency and phase deviations. The approach proposed here might be useful for high-speed reconfigurable beam scanning with high-power output.