Although topographic mapping missions and geological surveys carried out by Autonomous Underwater Vehicles (AUVs) are becoming increasingly prevalent, the lack of precise navigation in these scenarios still limits their application. This paper deals with the problems of long-term underwater navigation for AUVs and provides new mapping techniques by developing a Bathymetric Simultaneous Localisation And Mapping (BSLAM) method based on graph SLAM technology. To considerably reduce the calculation cost, the trajectory of the AUV is divided into various submaps based on Differences of Normals (DoN). Loop closures between submaps are obtained by terrain matching; meanwhile, maximum likelihood terrain estimation is also introduced to build weak data association within the submap. Assisted by one weight voting method for loop closures, the global and local trajectory corrections work together to provide an accurate navigation solution for AUVs with weak data association and inaccurate loop closures. The viability, accuracy and real-time performance of the proposed algorithm are verified with data collected onboard, including an 8 km planned track recorded at a speed of 4 knots in Qingdao, China.