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

$ curl repovive.com/roadmaps/data-structures/fenwick-trees/dynamic-frequency-queries

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

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

$ curl repovive.com/roadmaps/data-structures/fenwick-trees/dynamic-frequency-queries

Repovive

Dynamic Frequency Queries - Fenwick Trees | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Dynamic Frequency Queries

Multiset with BIT

BIT can implement a dynamic multiset supporting:

$\text{insert}(x)$ : add element $x$
$\text{delete}(x)$ : remove one occurrence of $x$
$\text{countLess}(x)$ : count elements $< x$
$\text{kth}(k)$ : find $k$ -th smallest element

Implementation:

def insert(x):
    update(x, +1)

def delete(x):
    update(x, -1)

def countLess(x):
    return query(x - 1)

def kth(k):
    return findFirst(k)

With coordinate compression, this handles any value range in $O(\log n)$ per operation.