Succinct bounded-sum array with $O(1)$ access

Assume we have a $n$ sized integer array $A$, and that we know that $\sum_{i\in[n]}A[i] \le M$.

Assume we are using the RAM model with $\Theta(\log n)$ sized memory words (which can be read / written in $O(1)$ time), and that $M=n^{O(1)}$.

A standard implementation could allocate $\lceil \log_2 M\rceil$ bits per cell, resulting in a $n\cdot \lceil \log_2 M\rceil$ bits array.

Arithmetic encoding allows us to encode the array using
$$\left\lceil\log_2{n + M \choose M}\right\rceil\approx n\log\left(\frac{M}{n}\right)$$

bits, but does not allow $O(1)$ time operations.


Is there a succinct encoding (say, of size
$n\log\left(\frac{M}{n}\right)+O(n)$) that allows $O(1)$ time
operations?

The required operations are standard array operations -- retrieving and setting the value of $A[i]$ for any $i\in[n]$.

Raman, Raman, and Rao is a standard reference for rank/select in O(1) time. This solves your problem for the special case of a static array, i.e., you can retrieve $A[i]$ in $O(1)$ time, but not update $A$: see the third bullet item in their abstract. The rank operation can be used to determine membership, and the select operation retrieves the $i$th element of the array. Their data structure requires $o(n)+O(\lg \lg m)$ extra space beyond the minimum.

The conclusion of their paper also mentions a lower bound if you want to support insert, delete, rank, and select. I don't know if that's applicable here.

StackExchange Computer Science Q#43821, answer score: 2