# 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$$. 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$$.

Posted on Categories Articles