Two major performance bottlenecks with decision tree based classifiers in a data stream environment are the depth of the tree and the update overhead of maintaining leaf node statistics on an instance-wise basis to ensure that classification is consistent with the current state of the data stream. Previous research has shown that classifiers based on Fourier spectra derived from decision trees produce compact array structures that can be searched and maintained much more efficiently than deep tree based structures. However, the key issue of incrementally adapting the spectrum to changes has not been addressed. In this research we present a strategy for incremental maintenance of the Fourier spectrum to changes in concept that take place in data stream environments. Along with the incremental approach we also propose schemes for feature selection and synopsis generation that enable the coefficient array to be refreshed efficiently on a periodic basis. Our empirical evaluation on a number of widely used stream classifiers reveals that the Fourier classifier outperforms them, both in terms of classification accuracy as well as speed of classification.