Original problem · C++ solution
Maintain the current array directly.
Maintain the current array directly. A type-one query overwrites one element; a type-two query reads the latest stored value at its index.
- Time: O(N+Q).
- Extra space: O(N).
A vector initializes its sized elements before use and provides zero-based indexing. Keep an input count separate from indices when the same count is needed later.
Translate one-based input indices once and keep every access within the allocated range.
State the invariant without looking at the code. Give one input that breaks the most tempting incorrect approach, then add it to the tests.