In this paper, we propose a radio environment map (REM) construction method that interpolates the received signal power over not only the spatial domain but also the frequency domain. REM is a tool for analyzing radio propagation, which is typically defined as a map that stores the received signal power. Crowdsourcing with spatial interpolation (e.g., Kriging) can accurately construct the REM, and the accurate REM improves the efficiency of spectrum use. However, crowdsourcing can only be performed over frequencies in which the mobile terminals can perform the sensing. Thus, conventional REM construction may only improve the spectral efficiency in the frequency in which the sensing can be performed. Our proposed method focuses on the fact that the average received signal power, which consists of path loss and shadowing, shows a strong correlation over the frequency domain. We show that utilizing correlations over both frequency and spatial domains can construct the REM even if the datasets are not available at the estimated environment.