Conversation

Notices

1. Embed this notice
   Lina Inver?e (lina@eientei.org)'s status on Thursday, 16-Jan-2025 16:09:44 JST Lina Inver?e

   in reply to

   • Not Elon Musk
   @xy nigga that's nuts :nuts:
   • Embed this notice
     Not Elon Musk (xy@mastodon.mit.edu)'s status on Thursday, 16-Jan-2025 16:09:45 JST Not Elon Musk

     in reply to

     And here's a Fenwick the squirrel who I folded 1.5 years ago. I guess his name is because he lives in a Fenwick tree or something. When I folded him last year, I told my friends there was a squirrel in my room and they thought a real squirrel was running around wrecking havok in my room 🤣

   • Embed this notice
     Not Elon Musk (xy@mastodon.mit.edu)'s status on Thursday, 16-Jan-2025 16:09:46 JST Not Elon Musk

     in reply to

     I haven't done benchmarks to confirm this, but Fenwick trees should use 1/4 the memory of segtrees and be somewhat faster since they use for loops and bit hacks instead of recursion.

   • Embed this notice
     Not Elon Musk (xy@mastodon.mit.edu)'s status on Thursday, 16-Jan-2025 16:09:46 JST Not Elon Musk

     in reply to

     The other weird thing about the "search for largest index with prefix sum less than or equal to s" operation is that it views the Fenwick array as an implicit binary tree while the update and query ops view the array as (two different) binomial trees. So maybe the tagline for Fenwick trees should be "One array. Three trees."

   • Embed this notice
     Not Elon Musk (xy@mastodon.mit.edu)'s status on Thursday, 16-Jan-2025 16:09:47 JST Not Elon Musk

     I wrote a fast Fenwick tree library for my flash cards app: https://git.unnamed.website/sdc/tree/fenwick.c

     The operation "Search for largest index with prefix sum less than or equal to s" isn't a common thing that people do with Fenwick trees so I had to read an arXiv paper about it.

     The nice thing about Fenwick trees is that they're only a few lines of code but... on the other hand they use crazy incomprehensive bit hacks!