#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/sqrt-decomposition/distinct-values-add-remove

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/sqrt-decomposition/distinct-values-add-remove

Repovive

Distinct Values - Add/Remove - Sqrt Decomposition | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Distinct Values - Add/Remove

Tracking counts

Maintain a frequency array $cnt[v]$ = count of value $v$ in current range, and $distinctCount$ = number of values with $cnt > 0$ .

Add operation:

function add(value)
    if cnt[value] = 0 then
        distinctCount := distinctCount + 1
    cnt[value] := cnt[value] + 1

Remove operation:

function remove(value)
    cnt[value] := cnt[value] - 1
    if cnt[value] = 0 then
        distinctCount := distinctCount - 1

Both are $O(1)$ . Total time: $O((n + q)\sqrt{n})$ .