Fillable arrays with constant time operations and a single bit of redundancy

Jacob Teo Por Loong, Jelani Nelson, Huacheng Yu

In the fillable array problem one must maintain an array A[1..n] of $w$-bit entries subject to random access reads and writes, and also a $\text{fill}(\Delta )$ operation which sets ev…