Template: Lazy-Fill Array

[ganmodokix]

Summary

Add Lazy Fill Array as follows:

• an array with random-access i/o
• can be updated all elements at time O(1)
• has an vector-like interface

Implementation

A lazy fill array has a extra fill value, an extra counter and an extra array to hold the counter value when each array element has last modified. Once update-all query comes up, the counter is incremented. Then, you can use counter_value == last_modified[i] to find whether each element value is still valid.