Peano Curve for Mo's Algorithm

Правка en1, от dedsec_29, 2023-04-29 14:49:36

Ever since I read this blog, I have been curious to see how other space-filling curves other than Hilbert can be used to reduce the run time. I chose the Peano curve.

Let's build a $$$3^k x 3^k$$$ matrix and visit all the cells on the matrix according to this curve. Then denote $$$\text{ord}(i,j,k)$$$ as the number of cells visited before the cell $$$(i,j)$$$ on the $$$3^k x 3^k$$$ matrix.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en18 Английский dedsec_29 2023-05-11 23:34:45 6 Tiny change: 'o see how other space-fil' -> 'o see how space-fil'
en17 Английский dedsec_29 2023-05-11 21:34:15 100 Tiny change: 'mit :D\n\n\n' -> 'mit :D\n\nThanks to [user:nor] for proof-reading the blog\n'
en16 Английский dedsec_29 2023-05-11 21:25:51 0 (published)
en15 Английский dedsec_29 2023-05-11 21:17:03 3151
en14 Английский dedsec_29 2023-05-10 17:50:48 380 Tiny change: 'q 8$. <br>\n![ ]' -> 'q 8$. <br><br>\n![ ]'
en13 Английский dedsec_29 2023-05-09 16:03:38 895 Tiny change: ' \sqrt{q})$\n\n# Use' -> ' \sqrt{q}).$\n\n# Use'
en12 Английский dedsec_29 2023-05-09 15:46:30 2725 Tiny change: ' 10^{6}$\n\n# Use ' -> ' 10^{6}$\n<br><br>\n\n# Use '
en11 Английский dedsec_29 2023-05-09 15:10:19 219 Tiny change: 'imgur.com/YojbCNS.png)\n![ ](https://i.imgur.com/' -> 'imgur.com/'
en10 Английский dedsec_29 2023-05-09 14:58:58 1211 Tiny change: ' k = 2 as 3^2 >= 8\n' -> ' k = 2 as $3^2$ >= 8\n'
en9 Английский dedsec_29 2023-05-09 14:22:35 103 Tiny change: 'ing way:\n\n' -> 'ing way:\n![ ](https://i.imgur.com/1MYmdIt.png)\n\n'
en8 Английский dedsec_29 2023-05-09 14:18:56 406 Tiny change: '4rS.png)\nEach row' -> '4rS.png)\n<br>\nEach row'
en7 Английский dedsec_29 2023-05-09 14:01:58 151 Tiny change: 'by $a$\n\n\n' -> 'by $a$\n\n2. Perform $\text{peano-flip} on each a_{i,j}$\n\n\n'
en6 Английский dedsec_29 2023-05-09 13:52:58 646
en5 Английский dedsec_29 2023-05-09 13:28:43 600 Tiny change: 'point.\n\nThis p' -> 'point.\n\n![ ](https://i.imgur.com/5uQUsDb.jpeg)\n\nThis p'
en4 Английский dedsec_29 2023-05-09 13:16:16 485 Tiny change: 'ach query (l,r) can be vi' -> 'ach query $(l,r)$ can be vi'
en3 Английский dedsec_29 2023-05-09 13:07:37 595
en2 Английский dedsec_29 2023-05-06 20:18:16 878
en1 Английский dedsec_29 2023-04-29 14:49:36 456 Initial revision (saved to drafts)