Algorithms / Fenwick Tree Prefix Sum
Least You Need to Know: Fenwick Trees, Prefix Sums, and Low-Bit Jumps
Fenwick trees support prefix-sum queries and point updates in `O(log n)` by storing carefully chosen partial sums. The key bit trick is the low bit, which tells how large a range each index is responsible for.
جو کم از کم جاننا ضروری ہے
- Fenwick trees are commonly implemented with 1-based indexing.
- Each tree index stores a partial sum for a range determined by its lowest set bit.
- Prefix-sum queries move downward by subtracting the low bit.
- A range sum can be computed from two prefix sums.
- Fenwick trees trade a little bit arithmetic for compact `O(log n)` operations.
اہم علامتیں
lowbit(x) = x & -x
size of the segment represented at index x
prefix(r)
sum of positions 1 through r
range(l, r)
prefix(r) - prefix(l - 1)
مختصر حل شدہ مثال
- Suppose you need many updates and prefix sums over an array.
- In a Fenwick tree, index `i` stores a sum covering the last `lowbit(i)` positions ending at `i`.
- To query `prefix(r)`, keep adding tree values and move `r` downward by `lowbit(r)`.
- The path length is logarithmic because each step removes the lowest set bit.
عام غلطیاں
- Students often mix 0-based array indices with the 1-based Fenwick convention.
- Fenwick trees answer prefix sums directly; general range sums come from prefix differences.
- `x & -x` isolates the lowest set bit, not the highest one.
اس قسم کے سوال کو کیسے پہچانیں
- The task needs many point updates plus prefix or range frequency/sum queries.
- The prompt is friendly to coordinate compression plus prefix counts.
- A full segment tree would work, but a lighter-weight prefix structure is enough.
Next recommended lesson
Continue through this topic with Least You Need to Know: Cycle Detection in Directed and Undirected Graphs.
Least You Need to Know: Cycle Detection in Directed and Undirected GraphsRelated lessons
Keep going with nearby lessons in the same topic.