Talk:Fenwick tree

Initial creation run time

Shouldn't it be possible to do the initial precalculation in O(n) time? (if you build it from bottom upwards, rather than one item at a time) MaZe Pallas (talk) 19:41, 14 January 2016 (UTC)[reply]

Yes, it is possible. Here's a link to an implementation and explanation: Is it possible to build a Fenwick tree in O(n)? Although I'm not sure if this should be part of the page. Maybe mention, that it is possible. Afaxnraner (talk) 08:38, 18 August 2016 (UTC)[reply]

Proposed merge with Prefix sum article

I propose merging this article with the article on prefix sums by adding a section on Fenwick trees to said article.

Andrew Helwer (talk) 21:13, 9 April 2012 (UTC)[reply]

It would be useful to mention Fenwick trees and other similar data structures (segment tree) in that article. But I think this article deserves to be expanded, rather than become a subsection in prefix sums. There's much to say to about Fenwick trees, the first external link points to a nice article about them. We should expand the article with at least details of how Fenwick tree is represented and how operations on it are performed. I think such level of detail would be too much for a subsection in another article. -- X7q (talk) 23:41, 9 April 2012 (UTC)[reply]

: All right, I'll see about expanding it first. Andrew Helwer (talk) 02:57, 10 April 2012 (UTC)[reply]

I oppose the merging and support X7q's position. WillNess (talk) 07:31, 8 July 2012 (UTC)[reply]

I agree with WillNess. Robertwharvey (talk) 23:31, 8 August 2012 (UTC)[reply]

The example is way too big and bloated

I have no idea why someone replaced the perfectly apt example at https://en.wikipedia.org/w/index.php?title=Fenwick_tree&oldid=736899871 with the current enormously bloated code at https://en.wikipedia.org/w/index.php?title=Fenwick_tree&oldid=805301708 that contains a ton of irrelevant stuff. I don't want to start an edit war, so can we vote to revert it? 185.31.142.251 (talk) 17:50, 17 November 2017 (UTC)[reply]

I agree with this. Since nothing changed between November 2017 and now I reverted the "Implementation" section to the nice and simple version that was there before. Hex539 (talk) 11:23, 7 May 2018 (UTC)[reply]

The implementation now seems over-simplified (without an init function) and uses one-based indexing which is counter-intuitive in C codes. Propose to revert it, but maybe remove the benchmark for clarity. 73.231.252.99 (talk) 01:19, 7 August 2018 (UTC)[reply]

Agreed that we're now over-simplified - efficient init is nontrivial (my O(n) was much more verbose, good thing I looked), though some other helpers seemed unnecessary. Also the current add function seems broken: i must be 1-based or updating the first element will never terminate, but I believe the condition should then be <= size or the last element of a power-of-two tree isn't updated. Fluppeteer (talk) 18:13, 13 November 2018 (UTC)[reply]

I tried to add the useful parts of the too-big example to the too-small example and thereby produce something in the Goldilocks zone. Now uses 0-based indexing and includes assertions to document the domain of valid inputs, but sticks with a single array and fixed SIZE, and omits the big test driver. Rm the Template:disputed tag; no idea what fact was actually disputed there (@Wqwt: wasn't it the animated illustration in the lead you were questioning?) 64.44.80.252 (talk) 07:25, 16 January 2021 (UTC)[reply]

I've simplified the code further and made some corrections. Split code into "basic implementation" and "useful functions".Dl.goe (talk) 13:18, 18 June 2021 (UTC)[reply]

Binary tree?

Is the animation presented even a binary indexed tree? It's certainly not a binary tree which is how the array implicit tree works.

Wqwt (talk) 13:46, 21 August 2019 (UTC)[reply]

Relation to "sum tree"

See https://www.fcodelabs.com/2019/03/18/Sum-Tree-Introduction/

I have not really dived into either of the concepts, but they seem strongly related at first glance. 2001:700:300:4221:3916:6608:BE75:CB88 (talk) 08:49, 13 September 2019 (UTC)[reply]

"Least significant bit"

In the comments to the C implementation, `i & (-i)` is described as the least significant bit which, based on the linked description should instead be computed as `i & 1`. I understand that instead returns the least significant bit that has value of 1. I corrected the comment to reflect that. Matteodellamico (talk) 08:07, 21 April 2022 (UTC)[reply]

Is the code for the get element function correct?

range_sum returns the sum from i+1 to j so get(i) would return the i+1th element, so its basically -1 indexed — Preceding unsigned comment added by Ymensss (talk • contribs) 15:26, 6 June 2022 (UTC)[reply]

strangely bad article

I rarely have anything but nitpicks with wiki articles but this one is just terrible. It gives no intuition of how it works, and the section <https://en.wikipedia.org/wiki/Fenwick_tree#Updating_and_querying_the_tree> well, I've read it several times over and I have no idea of what it's saying. It just makes no sense to me. Even the comments are baffling 79.79.245.61 (talk) 09:06, 19 July 2022 (UTC)[reply]

I know how a Fenwick tree works and I can't understand the article. 121.6.203.65 (talk) 09:51, 26 August 2023 (UTC)[reply]

@79.79.245.61 and 121.6.203.65: I just did a pretty major overhaul. Is it any better? 97.102.205.224 (talk) 15:24, 23 January 2024 (UTC)[reply]