Algorithms / Fenwick Tree Point Update
Least You Need to Know: Fenwick Point Updates, Frequencies, and Order Statistics
Point updates in a Fenwick tree climb upward through the indices whose stored partial sums include the changed position. This makes the structure especially useful for dynamic frequency tables and coordinate-compressed counting problems.
Least you need to know
- A point update adds a delta at one position and updates all Fenwick cells whose covered ranges include that position.
- Update traversal moves upward by adding the low bit.
- Each point update touches only
O(log n)cells. - Fenwick trees are great for dynamic frequency counting after coordinate compression.
- Prefix counts can answer ranking or k-th style questions with extra logic.
Key notation
- add(i, delta) — increase position i by delta
- i += lowbit(i) — move to the next Fenwick cell covering the point
- freq prefix — count of compressed values up to a rank
Worked example
- If index 6 increases by 1, update tree cells whose represented ranges contain position 6.
- In 1-based Fenwick code, repeatedly add the low bit:
6 -> 8 -> 16 .... - Each visited cell stores a partial sum that now needs the same delta.
- Only logarithmically many cells change.
Common mistakes
- Students sometimes use the query direction for updates and the update direction for queries.
- Coordinate compression preserves order, not original numeric spacing.
- Fenwick cells store aggregates over blocks, not direct copies of one array element each.
How to recognize it
- The prompt mixes many point updates with prefix/rank queries.
- Values may be large, but only relative order matters after compression.
- A compact logarithmic structure is enough; no arbitrary range updates are required.
Next recommended lesson
Continue through this topic with Least You Need to Know: Fenwick Trees, Prefix Sums, and Low-Bit Jumps.
Least You Need to Know: Fenwick Trees, Prefix Sums, and Low-Bit JumpsRelated lessons
Keep going with nearby lessons in the same topic.