There is some really cool engineering tricks involving a thing called a caisson.

https://en.wikipedia.org/wiki/Caisson_(engineering)

Basically it is a box to keep water out while they build the footings.

Build the box, pump water out, work in the relative dry while hoping pumps keep working and the box doesn't leak.

Another tool they used was driving pylons or piles deep into the ground. These could be put in place from barges or other floating platforms.

Another kind of bridge is like a rope bridge.

Send a small rope across with a projectile (or a person travelling the distance by boat and/or on foot) Use this rope to pull a larger rope across. Keep on bringing rope/cable across the gap until you have enough strength / support to build a bridge.

There are different types of bridges for different kinds of challenges.