Map overlay, any algorithm for face updating step?
Before we 'fill in' the value for the new faces at the halfedges,  we wait until the rest of the algorithm is finished, so we know which faces are still present in the end and only have to traverse every edge once. We do this by getting the halfedge that we have considered as a 'representative' and traverse the proper cycle until we return at our edge. So, our complexity is bounded by the sum of the faces and the edges, instead of their product, giving $O(n)$ instead of $O(n^2)$.

That book tends to ignore the subtleties that arise in dealing with DCELs. At first, it seems strange that updating faces would take only $O(n)$ time, since the face of the edge would get updated multiple times. Here, $n$ is 'the complexity of the subdivision', i.e. the sum of the edges and faces of the DECL.

However, since we only want to store the final face value at the end, we wait with the updating the face values of the half-edges until we have filled in everything else. We can store the new value at only one half-edge, which will be the 'representative' of that face and maintain a list of those half-edges. 

Then, at the final step, we fill in the face values for the cycles of the stored representative edges, by traversing the cycle associated with the half-edge until we return to the edge where we started and remove a (different) representative if we encounter it, since this means that the face it belonged to no longer exists. By doing so for every representative in the correct order (i.e. from the last created face to the first), we avoid traversing cycles for faces that do not occur in the final DECL. So, we are able to check every face and visit all edges after that, which means we get the required complexity of $O(n)$.