# 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]$.

"Improved Address-Calculation Coding of Integer Arrays" by Elmasry et al. may be state of the art: they store such an array in $n \lg(1 + M/n) + O(n)$ bits, perform point reads in $O(\lg \lg M)$ time, and perform point updates in $O(\lg^2 M)$ time.
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.
• I think what's going on is that Raman-Raman-Rao solves this problem for the special case of a sorted list, i.e., where the entries of $A$ appear in sorted order. For a sorted list, the select operation is exactly what you want (select(i) returns exactly $A[i]$). However, I'm not sure whether it can be extended to handle arbitrary lists, not necessarily sorted. (Cc: @RB) – D.W. Jun 22 '15 at 22:42
• I'm not sure why my previous comment was deleted, but this does not seem to allow get/set random access in $O(1)$ time which is what I'm looking for. – R B Jun 23 '15 at 13:12