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

Question

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

Answer 1

"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.

Answer 2

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.

• D.W.: 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)
• R B: 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.
• KWillets: For non-sorted, it may be possible to store the partial sums B[i] = sum(A[0..i-1]) of the elements, if they're >0, ie the resulting sequence is ascending, and O(1) reads for the static case. For the dynamic case, I think the bounds are worse; this is called the "dynamic partial sums" problem. See eg people.csail.mit.edu/mip/papers/sums/sums.pdf .