The idea of caching the information which buildings are in range of an effector-building (which you can cache either from the effector or in the affected) is definitely a good idea. Buildings (usually) don't move, so there is little reason to redo these expensive calculations. You only need to do it for buildings which are created or removed.
Whether or not a building is still connected to the road network isn't something you need to check every single frame (By the way, you might also find some ways to optimize this specifically by looking a bit into graph theory). It would be completely sufficient if buildings only check for that periodically every few seconds after the building was built (AND if there was a change to the road network). The same applies to building range effects. It is perfectly acceptable if a building only checks every few hundred frames "Am I still covered by at least one active fire department?"
So you could have your update-loop only do these expensive calculations for a few hundred buildings at a time for every update. You might want to give preferences to buildings which are currently on the user's screen, so they get immediate feedback for their actions.
Regarding using multithreading: City builders tend to be on the more computationally expensive side, especially if you want to allow players to build really large and if you want to have a high simulation complexity. So in the long run it might not be wrong to think about what computations in your game can be handled asynchronous.