but ice has another mechanism--frost cracking (water freezes in cracks and expands with great force). And if salt was used on the bridge, it could have damaged both concrete and steel.
Yes, although cracking from water intrusion is going to happen regardless of the presence or absence of reinforcement. The advantage of reinforced concrete is that a center crack won't matter as much, as the (presumed) hoops will hold it a footing or pier together. That's the idea: the concrete is very strong in compression but needs to be "held together" to have that strength.
However, generally what happens is that water intrusion finds the steel and rusts it, and like ice, the volume of rust is greater than the volume of steel, and so it spalls off the outer layer of concrete, and then since it's no longer embedded, the steel doesn't develop any strength with the concrete.
Salt getting into the steel is nasty, you end up with a cathodic (anodic?) reaction that will rot the steel right out from inside of the concrete. However, I would be very surprised if they were putting down salt on this bridge, that's very environmentally unsound. The bridge likely has scuppers that send runoff right into the lake.
Note that prestressing is used for precast concrete beams, and post-tensioning for either precast or cast-in-place beams, but you would not prestress a pier, footing, or piles.