Timeline for How do we know INVERSIONS-COUNT algorithm implemented in balanced tree really works?
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 18, 2017 at 6:04 | vote | accept | Yos | ||
| Jul 17, 2017 at 19:07 | history | edited | Yos | CC BY-SA 3.0 |
added 6 characters in body
|
| Jul 17, 2017 at 14:26 | answer | added | Yuval Filmus | timeline score: 3 | |
| Jul 17, 2017 at 11:14 | comment | added | Yuval Filmus |
I believe that RANK returns $i \geq 1$ such that node_x is the $i$th smallest element in the tree.
|
|
| Jul 17, 2017 at 7:59 | history | edited | Yos | CC BY-SA 3.0 |
added more details about helper functions
|
| Jul 17, 2017 at 7:46 | history | edited | Yos | CC BY-SA 3.0 |
added the definition of order statistics tree
|
| Jul 17, 2017 at 7:38 | comment | added | Yuval Filmus | Presumably you can prove the correctness of the algorithm by induction. | |
| Jul 17, 2017 at 6:37 | history | asked | Yos | CC BY-SA 3.0 |