Inversion counting with swap queries in O(log N)
Difference between en2 and en3, changed 0 character(s)
I am currently working on the following problem:↵

- Given a permutation $A$ of length $N$, you have $Q$ queries specifying 2 numbers $X$ and $Y$ that swap the elements at indices $X$ and $Y$. After every query, output the number of inversions in the new permutation. All queries must be answered online.↵

My current solution can process every query in $\log^2$ $N$ per query and $N$ $\log$ $N$ precomputation, by first precomputing the number of inversions in the initial permutation and using a segment tree with a BBST in every node. Each BBST stores all of the elements in the range covered by the segment tree node. ↵

We perform a range query on the value at index $X$ and the value at index $Y$ to determine the number of numbers smaller than either number in the segment between them, and then compute the change in inversions. After that, we update the 2 indices in the segment tree. Each of the $\log$ $N$ nodes takes $\log$ $N$ time to update, which gives an overall complexity of $\log^2$ $N$.↵

My question is: Is it possible to compute the change in inversions more quickly than $\log^2$ $N$? eg. computing the change in $\log$ $N$ time. I suspect that it is possible with either a modification to the segment tree, or using a completely different data structure all together. Any ideas are welcome :)↵


  Rev. Lang. By When Δ Comment
en3 English bensonlzl 2020-02-15 11:22:06 0 (published)
en2 English bensonlzl 2020-02-15 11:21:50 361 Tiny change: ' query in $O(log^2 N)$ per query' -> ' query in log^2 N per query'
en1 English bensonlzl 2020-02-15 11:18:53 1019 Initial revision (saved to drafts)