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.