Inversion counting with swap queries in O(log N)

Revision en1, by bensonlzl, 2020-02-15 11:18:53

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 $$$O(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.

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.

Tags inversions, data structure

History

 
 
 
 
Revisions
 
 
  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)