Dynamic Frequency Queries

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.