Mode Query - Data Structures

You need two structures:

$1.$ $cnt[v]$ = frequency of value $v$ in current range

$2.$ $freqCount[f]$ = how many values have frequency exactly $f$ Also track $maxFreq$ = current maximum frequency. When adding value $v$:

• Decrease $freqCount[cnt[v]]$
• Increase $cnt[v]$
• Increase $freqCount[cnt[v]]$
• Update $maxFreq$ if $cnt[v] > maxFreq$ When removing: similar, but $maxFreq$ might decrease. If $freqCount[maxFreq]$ becomes $0$, decrement $maxFreq$.