Skip to main content

Segment Trees and Fenwick Trees for Range Queries

What This Concept Is​

A segment tree aggregates intervals using an associative operation and identity; commutativity is not required if left-to-right order is preserved. The lab implements integer sums with half-open intervals [l,r), including empty sum 0. A Fenwick tree compactly stores aligned prefix blocks and supports integer point-add/prefix-sum; range sums subtract two prefixes.

Why It Matters Here​

These are related but not identical capabilities. Arbitrary range minimum cannot be obtained by subtracting prefix minima. Lazy updates require a defined action on aggregates and a correct composition order, not a blanket promise for every operation.

Concrete Examples​

Fenwick blocks. Internally use one-based i and lowbit(i)=i&(-i). Cell i stores array positions [i-lowbit(i),i) in the external zero-based half-open notation. Prefix(end) repeatedly subtracts lowbit; point add starts at index+1 and repeatedly adds lowbit. Starting an update at internal 0 would never progress. The reference constructs all blocks in O(n), rather than calling an O(log n) add for every input item.

Lazy sum action. Represent add d by affine tag (a,b)=(1,d) and assignment v by (0,v), acting as x -> a*x+b. On a segment of length L with sum S, new sum is a*S+b*L. If old tag is (a1,b1) and a new tag arrives (a2,b2), compose new after old: (a2*a1, a2*b1+b2). Forgetting L or reversing composition breaks the update.

For [1,2,3,4], assign all to 5 then add 3 gives [8,8,8,8]. Add 3 then assign 5 gives [5,5,5,5]: the updates do not commute. Assignment to zero must remain a real pending tag, distinct from no update. Push a pending action before partial descent; combine child sums after partial updates.

Both structures use O(n) storage and O(log(n+1)) per valid query/update, with O(n) construction in the reference. Outputting every element still takes additional work. 4n is a convenient upper allocation bound for one recursive layout, not the definition or exact number of segment-tree nodes.

Common Confusion / Misconceptions​

Associativity alone does not justify a lazy action. Generic noncommutative aggregation must preserve operand order. Fenwick invertibility/commutativity requirements depend on supported updates; this core uses the additive integer group. Negative array values invalidate some prefix-sum selection tricks even though ordinary sums remain valid.

How To Use It​

Define intervals, identities, point-add versus point-set and action composition. Compare long mixed add/assign/query traces to a plain list, leaving tags pending across several updates. Test zero assignment, negative values, empty intervals, whole ranges and sizes not powers of two. Inspect Fenwick block meanings independently.

Check Yourself​

Why does range sum use an inverse? Why does add need segment length? Which tag represents assignment to zero? Why must a pending tag be applied in chronological order?

Mini Drill or Application​

Start [1,2,3,4], add 2 on [1,4), assign -1 on [2,4). Feedback: [1,4,-1,-1], total 3 and sum [1,3)=3. Derive the tags rather than only updating a plain list.

Read This Only If Stuck​

Competitive Programming: segment and Fenwick trees through the local contents index. The affine action derivation above specifies the lab’s add/assign extension independently of source indexing conventions.