Data structure for querying maximum of a rolling total

Question

Let $A = \{a_1, \ldots, a_n\}$ be a set of numbers and $w$ be some number. Define $p_w^{A}: \mathbb{R} \rightarrow \mathbb{N}$ as $$p_w^{A}(r) = |\{i \in \{1, \ldots, n\} | r \leq a_i \leq r + w\}|.$$ Note that $p_w^{A}(\mathbb{R})$, the image of the whole $\mathbb{R}$ under $p_w^A$, is finite. Define $MRT_w(A) = \max p_w^{A}(\mathbb{R})$.

Let's fix a number $w$. The task is to implement a data structure which can store a set of values and has the following interface:

• Add value.
• Remove value.
• Compute $MRT_w(A)$, where $A$ is the set of all values which are currently stored in a data structure.

Can you get an $O(\log n)$ complexity for all 3 operations?

Answer 1

Consider a data structure (call it $D$), which can store pairs of $(key, value)$ (where $key$ and $value$ are some numbers) and has the following interface:

1. Put $(key, value)$ pair to a data structure (if such key is already in a data structure then ignore this operation). We will refer to this operation as $D.put(key, value)$.
2. Remove $key$ from a data structure. Denotation: $D.remove(key)$.
3. Given a pair of numbers $(l, r)$ and number $v$, consider all keys, which are currently stored in a data structure such that $key \in [l, r]$. Add number $v$ to all values, which are paired with those keys. Denotation: $D.add(l, r, v)$.
4. Given a pair of numbers $(l, r)$, consider all keys, which are currently stored in a data structure such that $key \in [l, r]$. Return a maximum of all values, which are paired with those keys. Denotation: $D.get\_max(l, r)$.

We can implement such a data structure so that all operations will have a worst-case time complexity $O(\log n)$. For a detailed discussion about this data structure you can refer to this question.

Now let's describe how to implement the data structure from the current question. First of all, if the data structure currently contains numbers $A = \{a_1, \ldots, a_n\}$ then to compute $MRT_w(A)$ it's sufficiently to consider numbers $p_w^A(a_1), \ldots, p_w^A(a_n)$. So let's create a data structure $D$ (from the firs part of the answer) and store there pairs $(a_i, p_w^A(a_i))$. There are 2 main questions that should be answered:

1. How to compute $p_w^A(a)$ when we try to put a new number $a$ into our data structure?
2. How to update values in $D$ during put and remove operations?

Data structure $D$ is implemented on the basis of a binary search tree. So when we put a new number $a$, we can easily compute a number of keys in a data structure, which lie in a segment $[a-w, a+w]$. And this number exactly equals to $p_w^A(a)$. Moreover, the keys which values should be affected by operation $D.put(a, p_w^A(a))$ form a continuous interval and their values lie in a segment $[a-w,a]$. So before we actually call $D.put(a, p_w^A(a))$, we should call $D.add(a-w, a, 1)$.

The same idea works when we remove some key $a$ from our data structure. It affects only consecutive interval of keys, which values lie in $[a-w,a]$ and it decrements their values. So before we call $D.remove(a)$, we should call $D.add(a-w, a, -1)$.

Computation of $MRT_w(A)$ is done by calling $D.get\_max(min, max)$, where $min$ and $max$ are minimal and maximal keys, which are currently stored in a data structure.