A memory device can include a memory cell array and a remap data structure. A remap data structure can include a mapping history section configured to store sets of mappings between logical addresses and the physical addresses of the regions, and a status section configured to identify one of the sets of mappings as a live set for the device. Control logic can be coupled to the memory cell array and the remap data structure and configured to enable access to the storage locations and remap data structure. Firmware update systems and methods, including firmware-over-the-air (FOTA), that include a memory device are also disclosed.