Not sure about zstd, but in xz the blocks (frames in zstd) are stored across the file and linked by offsets into a linked list, so you can just scan over the compressed file very quickly at the start, and in memory build a map of uncompressed virtual offsets to compressed file positions. Here's the code in nbdkit-xz-filter:

https://gitlab.com/nbdkit/nbdkit/-/blob/master/filters/xz/xz...