Space Requirement

To update the results of any query $q$ , CPM needs to maintain the extra book-keeping information (i.e., visit list and heap).