Constant-time distinct-size counter
= Constant-time distinct-size counter
{title2=$D=|\{i:c_i>0\}|$}
Maintain a counter equal to the number of positive count-<array> entries. Increment it only when an <addition> changes zero to one; decrement it only when a removal changes one to zero. Other count changes leave the support unchanged. Initialization at zero and these cases prove the <representation invariant> by <induction> over completed operations, giving a constant-time distinct-size query.