Authenticated Encryption Sheme with Random Access and proven security?
First, authenticated encryptions based on universal MACs (UMACs) can have their tags computed from blocks of message in random order. This is because UMACs are often based on integer or binary polynomial addition and multiplication, which are associative and commutative operations. Based on this, AES-GCM and ChaCha20-Poly1305 may satisfy your needs.
For these algorithms, recomputing the hash state for 1 block requires some addition, multiplication, and exponentiation, where the exponentiation can be done using square-and-multiply approach.
Second, authenticated encryptions are supposed to operate on whole messages. From your description I sensibly believe this may be some type of XY problem, and you may need to disclose your application blueprint so that we may tell if better solutions to your ultimate problem exist.