An innovative approximate explicit model predictive control strategy is proposed. A multilevel approximation scheme for state space partitioning is applied, which relies on an adaptive domain decomposition strategy using multidimensional tree techniques. Polytopes are generated from such state space partitioning, for which equivalent state feedback gains are computed such that approximate explicit controls can be simply computed. The proposed scheme requires no online optimization and thus computing control using pre-computed control gains is extremely fast. Through an application to autonomous vehicle lateral control, it is shown that the proposed method can achieve a significant improvement of computation time and approximation quality over other approximate predictive control methods.