Timeline for BIT: What is the intuition behind a binary indexed tree and how was it thought about?
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 7, 2022 at 23:11 | comment | added | Andes Lam | i think you are both right. but intuition is a matter beyond correctness and a right solution solution can also be extremely "wrong" in intuition, so to speak. What I would like to add on is about the last set bits, aka the least significant bit. When I read the paper, Fenwick said instead the branching ratio depends on the number of trailing zeros. That's as far as I can see in the paper. What I can infer is that not only the branching ratio determines the number of attached nodes, but also the amount of partial sum. say 8, (1000), it can hold 8 nodes, including itself, hence 8 partial sum. | |
| Aug 13, 2018 at 5:22 | history | edited | ihadanny | CC BY-SA 4.0 |
added 12 characters in body
|
| Aug 4, 2018 at 16:19 | history | answered | ihadanny | CC BY-SA 4.0 |