4
$\begingroup$

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

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
0
2
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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) $\endgroup$
    – D.W. ♦
    Commented Jun 22, 2015 at 22:42
  • $\begingroup$ 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. $\endgroup$
    – R B
    Commented Jun 23, 2015 at 13:12
  • $\begingroup$ 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 . $\endgroup$
    – KWillets
    Commented Jun 23, 2015 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.