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.

The 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

Tiny 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 this kind of problem

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.