Title: In-Place Initializable Arrays,
Abstract: Initializing all elements of an array to a specified value is a basic
operation that frequently appears in numerous algorithms and programs.
Initializable arrays are abstract arrays that support initialization as well as
reading and writing of any element of the array in less than linear time
proportional to the length of the array. On the word RAM model with $w$ bits
word size, we propose an in-place algorithm using only 1 extra bit which
implements an initializable array of length $N$ each of whose elements can
store $\ell \in O(w)$ bits value, and supports all operations in constant worst
case time. We also show that our algorithm is not only time optimal but also
space optimal. Our algorithm significantly improves upon the previous best
algorithm [Navarro, CSUR 2014] using $N + \ell + o(N)$ extra bits supporting
all operations in constant worst case time.
Moreover, for a special cast that $\ell \ge 2 \lceil \log N \rceil$ and $\ell
\in O(w)$, we also propose an algorithm so that each element of initializable
array can store $2^\ell$ normal states and a one optional state, which uses
$\ell + \lceil \log N \rceil + 1$ extra bits and supports all operations in
constant worst case time.