Algorithm : Median of a dynamic array

Question

This question is inspired by this SPOJ problem. That problem asks median of the final array, that can be done in $O(k+n)$, where k is the number of update queries and n is the size of the array.

The variant : Given an array of length N (of the order $10^5$), initially all elements are 0. There are K (of the order $10^5$) queries of type A B, meaning array elements in range $[A,B]$ must be increased by 1. After every query operation, find the median of the array.
Can this be solved efficiently (subquadratic time, ie, better than $\Omega(N^2$)?

Answer 1

UPD: O$(N \sqrt N)$ solution

Bucketing

Let's split the array into blocks of $\sqrt N$ size. For each block let's keep all values in it in an array.

Let's also keep pairs $(Number, Count)$, counting the occurrences of each number, present in the block. We will also keep these pairs in an array, sorted by the $Number$. We also keep partial sums for this array, for each $Number$ indicating number of numbers less than this, in this block. (In the beginning this can be precalculated in $O(N log N)$ ).

Let's also keep a value $Mod$, that indicates that in reality all numbers in these block are not as they are saved, but actually bigger by $Mod$. Last, for each block let's keep a pointer in the array of pairs, pointing to the first $Number$, such that $Number+Mod$ is more than or equal to the current value of the median.

Answering query

Let's count total number of values in all blocks less than the median - simply sum all partial sums for pointers. Let's also count number of values equal to the median - by summing second components of pairs, at which our pointers point. This takes $O(1)$ for each block and therefore $O(\sqrt N)$ for each query.

If we found out that total number of values less than or equal to the median is less than ${N \over 2} + 1$, we may need to shift some of the pointers forward, since the value of median then increases by 1. In total each query we will at most need to shift $\sqrt N$ pointers by 1, making in total $O(N \sqrt N)$ shift forward.

Updating query $(A,B)$

For blocks fully covered by the interval we can simply increase the $Mod$ values. After that some of the pointers may need to be shifted backward by at most 1, to keep their invariant (pointing at first number more than or equal to the current median). Total number of shifts backwards won't exceed $O(N \sqrt N)$ for one query.

For two blocks half covered by the query let's update values in the array in the naive way:

First, increase each of them by $Mod$ and also increase each value in our sorted array of pairs by $Mod$. Clear $Mod$.

Then let's create a hash map of all values increased by 1 in the query.

Then let's loop through array of pairs and for each $Number$ we decrease it's $Count$ by an appropriate number in the hash map, and create an entry in the second array of pairs, indicating $(Number + 1, Count)$. Once we finish, we will have all numbers in our block presented by 2 array of pairs, both sorted by the first components. Then we can merge these to in the $O(\sqrt N)$.

Finally, recalculate partial sums for this new merged array and naively find the position of the pointer by looping through it.

Seems to be it, $O(\sqrt N)$ per query but I wouldn't want to code it;)

================================================================================

Here is an idea for $O(N \sqrt{N} log N)$ solution.

Observation: (Intuitive, Beautiful, Tested but Unproven):

By increasing the subarray by 1 we can only increase the median

• By 0 or 1, if array has odd length
• By 0 or 0.5 or 1, if array has even length

I tested this hypothesis extensively locally.

Let's assume $N \approx K$.

Bucketing

Then let's split our queries into $\sqrt N$ groups $\sqrt N$ each. At the beginning of each block we do the following:

• Calculate the median. Let it be $M$.
• Let's introduce $L=M-\sqrt N$, $R=M+\sqrt N$, $LC$ - number of elements less than $L$ in the array.
• For each value $X$ between $L$ and $R$ create a sorted list of all positions, in which value $X$ currently resides. We will keep each list as an implicit cartesian tree (data structure that allows cutting and merging subarray in $O(log Length)$. Example - STL Rope). This is the most computationally expensive step of the above and it takes $O(N log N)$ in the worst case, making overall complexity of these steps for all query groups $O(N \sqrt{N} log N)$.

Answering

When we will want to find the median, we will go through all values of $X$ between $L$ and $R$ and calculate sum $LC + CN(L) + CN(L+1) + CN(L+2)+ \cdots$ until it exceeds ${N \over 2} + 1$ for some value $L+t$ which will be new median. (Or average of two consecutive values). Here $CN(L)$ denotes number of items in the sorted list that corresponds to value $L$.

Updating

When we will want to update our structure after the next query ($A$, $B$), we will do the following:

• For each $X$ between $R$ and $L$ find subarray that contains all values between $A$ and $B$ (if we, for example, keep in the node of implicit cartesian tree minimum and maximum values in the corresponding subtree, we can find the appropriate indexes of subarray in $O(log N)$).
• Erase the corresponing subarray and insert a subarray, obtained the same way from the previous list.
• For list with numbers equal to $L$ we don't insert anything since we know that all values less than $L$ will stay less than $L$ in the scope of next $\sqrt N$ queries so we simply add them during summation as variable $LC$
• Splitting and merging implicit cartesian tree requires $O(log N)$ operations, we have $O(\sqrt N)$ cartesian trees, and our actions happen for each of $O(N)$ queries, leaving total complexity at $O(N \sqrt N log N)$.

Finally, we can save all queries in current block and then update our array, for example in $O(N + \sqrt N log \sqrt N)$ time by sorting queries and using scanline.

Afterthoughs:

I wonder if, since median can only increase by 1 or 0.5, we can solve this problem in $O(N log N)$ time somehow. Also, same as in the answer above, it may be possible that $O(N \sqrt N log N)$ can be optimized to $O(N log^2 N)$, although it is not obvious to me, how.

Answer 2

Assuming you're still in SPOJ context, you probably want a $\mathcal{o}(n^2)$ solution to fit the $1$ second time limit.

Here's a complicated solution that uses $\mathcal{O}(n)$ memory and has an $\mathcal{O}(n\sqrt{n} \log^2{(n)})$ runtime (whew!) assuming $\mathcal{O}(n) = \mathcal{O}(k)$. It probably wouldn't execute in a second, but might fit within 5-10.

NOTE: I'm going to conjecture that a $\mathcal{o}(n \log^3{n})$ solution is possible. This follows from my use of $\sqrt{n}$ buckets, and in my experience buckets can always be replaced by a tree (Splay?) for a $\mathcal{O}(\log{n})$ instead of $\mathcal{O}(\sqrt{n})$. Additionally I use a binary search that seems excessive. As a general rule of thumb, if the memory and time bounds are not balanced, you can improve one or the other until they are.

Insights:

Not truly online

In these problems, normally all the input is digested before any output is expected. We can use the information for all of the queries, before answering any of them. Even if it was interactive, this strategy would still work if $k$ was known ahead of time.

Replace the array

In the original problem, there are $\mathcal{O}(n)$ intervals of interest. These intervals are created by the start and end points of the $[A, B]$ query ranges. Intuitively, imagine dropping all of the start / end values on a number line. This creates the intervals, $x_1,x_2, \cdots, x_m$, where $m \le n$. In the original problem, you realized that all the "haystacks" or array elements in any $x_i$ take the same value or height. Effectively, the $x_i$ are our smallest unit of concern.

Bucketing

If we group the intervals into $\sqrt{m}$ buckets of size $\sqrt{m}$, you can update any range of intervals in $\mathcal{O}(\sqrt{n})$. This will be clearer later.

Select augmented BST

It's well known that by storing the size of the sub-tree of each node, counting the elements less than some cutoff takes $\mathcal{O}(\log{n})$ time. We'll be storing the sum length of intervals instead, but the operation is identical.

Binary Searching for the Median

If we have an efficient way to count how many "haystacks" are under a given height, we can binary search to find the median.

Setup:

Let $p = \sqrt{m}$.

Now we create buckets, $b_1 = [x_1, x_2, \cdots, x_{p}], b_2 = [x_{p + 1}, \cdots], \cdots, b_p = [x_{(p-1)p+1}, \cdots, x_m]$. We group the $x_i$ into $p$ clumps of size $p$. Each bucket has a corresponding "offset", $s_i = 0$, which is just a counter per bucket.

For each $b_i$, build a augmented BST $BT_i$ out of $x_u \in b_i$ keyed on the height of $x_u$. Each node in $BT_i$ will store the sum of the lengths of the intervals in its subtree, this is a well-documented strategy and can be maintained in $\mathcal{O}(\log{n})$ per operation. Remember that the length of an interval is in units of "haystacks", the number of array elements contained.

The $BT_i$ is purely to be able to answer in $\mathcal{O}(\log{n})$:

How many "haystacks" have height under $v$?

Dirty Stuff:

Iterate through the $k$ queries and update the data structure. This involves:

1. Update all affected $x_i$. If the query range completely encompasses any $b_j$, just add $1$ to $s_j$. Otherwise, manually update the $x_i$ in $BT_j$, which takes $\mathcal{O}(\log{n})$. There are at most $\sqrt{m}$ of each case, for a $\mathcal{O}(\log{(n)} \sqrt{2n})$ runtime.

2. Binary search for the median in the range $[0, k]$. We choose some guess $v$, and then ask all $\sqrt{m}$ $BT_i$ how many elements have height or value under $v$. In the BST select algorithm, we include the offset $s_i$ without affecting the runtime. This process takes $\mathcal{O}(\log{(k)}\log{(m)}\sqrt{m})$ or $\mathcal{O}(\log^2{(n)}\sqrt{n})$. Return when $v$ is the median.

There are $k \le n$ queries, for a $\mathcal{O}(n \sqrt{n} \log^2{(n)})$ total runtime, with $\mathcal{O}(m) = \mathcal{O}(n)$ memory, since we have constant storage for each $x_i$ and $s_u$.

I left out a lot of the details. Reply in the comments if you have questions, or if this approach has mistakes. Also this solution follows my hacky, inelegant style. Hopefully someone comes along with a cleaner, faster solution.

Answer 3

Consider a sequence $(A_i,B_i)_{i=1}^k$ of update queries, i.e. $1 \leq A_i \leq B_i \leq n$ for all $i \in [1..k]$. I will show how to solve the problem in time $\Theta(K \log n)$ and space $\Theta(n)$ where $K = \sum_{i=1}^k (B_i - A_i + 1)$.

Idea: Keep a sorted copy of the counter array and maintain pointers back and forth. When an entry is increased to be larger than its right neighbour -- say this one has value $c$ -- swap it across the block of subsequent entries with value $c$; the correct position can be found with binary search.

Algorithm: Assume that we have array A of length $n$ with pointers and array B of the same length with pairs of numbers and pointers. Initially, we have A[i] = i and B[i] = [0,i] for all i.

Then, the algorithm is as follows:

for each (a,b) in Updates {
  for i = a to b {
    j = A[i]
    B[j][0] += 1

    if ( B[j][0] > B[j + 1][0] ) {
      j' = BinarySearchInB(B[j + 1][0] + 0.5)
      i' = B[j][1]

      // Swap everything
      B[j][0]  -= 1
      B[j'][0] += 1
      A[i'] = j
      A[i] = j'
      B[j][1] = i'
      B[j'][1] = i
    }
  }
}

We assume that BinarySearch returns the index in B left of the gap the passed value belongs in; this is the right-most index with value B[j + 1][0] = B[j][0] - 1.

The algorithm clearly has the claimed cost. If $K \in o(n^2)$, this algorithm is indeed subquadratic.