Online state-time trajectory planning in highly dynamic environments remains an unsolved problem due to the curse of dimensionality of the state-time space. Existing state-time planners are typically implemented based on randomized sampling approaches or path searching on discrete graphs. The smoothness, path clearance, or planning efficiency is sometimes not satisfying. In this work, we propose a gradient-based planner on the state-time space for online trajectory generation in highly dynamic environments. To enable the gradient-based optimization, we propose a Timed-ESDT that supports distance and gradient queries with state-time keys. Based on the Timed-ESDT, we also define a smooth prior and an obstacle likelihood function that are compatible with the state-time space. The trajectory planning is then formulated to a MAP problem and solved by an efficient numerical optimizer. Moreover, to improve the optimality of the planner, we also define a state-time graph and conduct path searching on it to find a better initialization for the optimizer. By integrating the graph searching, the planning quality is significantly improved. Experiments on simulated and benchmark datasets demonstrate the superior performance of our proposes method over conventional ones.