time complexity – Faster algorithm for specific inversion count (part 2)

Each $j$ contributes $1$ to all $K'(sigma)_i$ with $j < i < sigma_j$.

Ideally you want a data structure that maintains a collection of $n$ counters $C_0, dots, C_{n-1}$ under the following operations:

  • Offset($j$, $delta$): Given $j$ and $delta$, add $delta$ to each $C_i$ with $i le j$.
  • Evaluate($i$): Return the value of $C_i$

When $sigma_j$ is revealed, you can add $1$ to all $C_i$ with $j < i < sigma_j$ (assuming the interval is non-empty) by performing the following two operations: (i) Offset($sigma_j-1$, $1$), (ii) Offset($j$, $-1$).
Then, you can recover the value of $K'(sigma)_i$ by performing a Evaluate($i$) operation.

The rest of the answers describes how to implement a data structure supporting each of the above operations in $O(log n)$ time, so that the overall time complexity will be $O(n log n)$.

Suppose for simplicity that $n$ is a power of $2$, so that $k = log n$.
Instead of keeping a single set of counters $C_0, dots, C_{n-1}$ (i.e., one for each $i$) keep multiple counters per element $i$.

The counters associated with $i$ will be $C^{(h)}_i$ for some suitably chosen values of $h$.
In particular, if the binary expansion of $i$ has $ell_i$ zeros in its least significant bit, then we will keep $ell_i$ counters $C^{(0)}_i, C^{(1)}_i, dots, C^{(ell_i-1)}_i$. (If $ell_i=0$, we keep no counters). The intuition is that adding $1$ to $C_i^{(h)}$ corresponds to adding $1$ to each of the $2^h$ “original counters” $C_i, C_{i+1}, dots, C_{i+2^{h}-1}$. In particular we say that $C_i^{(h)}$ covers $C_i, C_{i+1}, dots, C_{i+2^{h}-1}$.

See the figure for a graphical example with $n=16$.

example

To implement Offset($j$, $delta$): write $j+1$ as a sum of (at most $log n$) decreasing distinct powers of $2$ so that $j+1 = 2^{h_1} + 2^{h_2} + 2^{h_3} + dots + 2^{h_m}$. Do the following:

  • Set $x = 0$.
  • For each $ell = 1, dots, m$:
    • Increment $C^{(h_ell)}_x$ by $delta$.
    • Increment $x$ by $2^{h_ell}$.

For example when $j = 12$, we can write $j+1 = 13$ as $8 + 4 + 1 = 2^3 + 2^2 + 2^0$.
To perform Offset($12$, $1$), we would add $1$ to $C_{0}^{(3)}$, $C_{8}^{(2)}$, $C_{12}^{(0)}$. These are exactly the counters corresponding to the intervals highlighted in red.

To recover the value of the “original counter” $C_i$, it suffices to sum the values of all counters $C_{i’}^{(h)}$ that cover $C_i$.