Fenwick Trees are often introduced as a compact implementation trick for prefix sums.
But the interesting part is not the code. The interesting part is the binary structure underneath:
why ranges partition the way they do what i & -i is actually extracting how prefix traversal emerges naturally from binary decomposition why both updates and queries become logarithmic
I made a video trying to build intuition for these ideas visually and structurally rather than treating BIT as something to memorize.
Topics covered:
- naive approaches and prefix sums
- lowest set bit (LSB)
- derivation of i & -i
- block size interpretation
- traversal logic
- implementation walkthrough
Video: YouTube link Would genuinely appreciate feedback from experienced CP users on the content, and from people learning if its easier to understand especially if there are cleaner ways to think about or explain the structure.
References:
A New Data Structure for Cumulative Frequency Tables: https://blogs.asarkar.com/assets/docs/algo...
Fenwick Tree (Competitive Programming): https://cp-algorithms.com/data_structures/...
A question to test out your knowledge: https://codeforces.me/contest/2227/problem/G
Don't know whether it's mentioned in the video, but I love the idea that the structure of Fenwick tree is basically the segment tree with every right segment removed.
Ahh, i should've used this POV. will write it in the description if you don't mind :P
sure, why not
https://en.algorithmica.org/hpc/data-structures/segment-trees/#fenwick-trees here it is
damn, i really like the explanation over here, especially the comparisons, thanks for sharing
No problem, I had the same reaction when I first read it; algorithmica is truly an amazing resource
True, gonna use it for segment tree as well if its there
I don't know this. Could you tell me why?
In my opinion, BIT(Binary Indexed Tree) is from 1 to n by lens are always $$$2^k$$$.
But SegmentTree is always make the lens into half, lens will be any digits.
So I'd more glad to consider it as the Prefix Sum array which is splited by some sections.
And this is my blog: BinaryIndexedTree, writen by Chinese.
We only use set bits to assign the prefix sum of a range, Think of it in this way 13 -> (1101) in binary form so we need bit[13]+bit[12]+bit[8].I think u do understand how it works so Not elaborating but the essence is that since each number is unique on a binary number system, the way to accumulate the value is also unique. Also yes it is like a prefix sum but the range is variable for each type like the example i showed bit[12] is [9,12] range prefix and bit[8] is [1,8].
yeah, that intuition is actually very reasonable
a BIT can indeed be viewed as a compressed prefix sum structure where each index stores the sum of a 2^k sized segment ending at that index. So the decomposition is heavily tied to binary representation and intervals of length (2^k).
a Segment Tree is more general because it recursively splits intervals in half, so segment lengths are not restricted to powers of two during traversal/query composition.
So conceptually:
also, your explanation through binary decomposition is very elegant
Especially the viewpoint that BIT is not really a "tree" in the classical sense, but rather a binary partitioning of prefix information, makes the blog easier to like grasp and understand
The connection between lowbit and interval length is explained very cleanly in your writeup as well :)
Auto comment: topic has been updated by tee_01 (previous revision, new revision, compare).