I am trying to design an algorithm for a problem, and the following is an auxiliary problem for which a good solution would imply a faster algorithm for the original problem.

I am given access to an array of numbers. However, I am only allowed to query it by specifying an arbitrary subset of indices, in response to which I am then given the sum of the elements at those positions. These queries are quite costly, specifically they run in time $ \tilde{O}(n^2)$ time (where $ \tilde{O}(\cdot)$ hides polylogarithmic factors). I want to determine the element at each index in the array (i.e. reconstruct the array) using as little time as possible.

Of course, it is possible to do this by querying each element on its own. This algorithm does $ n$ queries and hence has total running time $ \tilde{O}(n^3)$ . I am wondering if there is a faster way. Adaptivity does not help with this problem, so any algorithm would have two steps: First, it executes a fixed sequence of queries, and then reconstructs all elements using the query answers. Ideally, both steps run in time $ o(n^3)$ . So far, any set of $ o(n)$ queries that I looked at makes recovery impossible. This might be the case for any such set of queries (and my intuition screams that this is probably the case), but I cannot see a proof for this.

I’d love an answer that either shows a faster algorithm or proves that $ o(n)$ queries are impossible, but answers with partial insights would also be great.