Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 19m 29s17 days 22 hours 19 minutes 29 seconds.

Advanced - Data Structures and Range Queries · 4:38

Fenwick - Range Updates, Range Queries, 2D, Prefix-Min

A Fenwick tree over the difference array turns a range update into two point updates, with a point value read back as a prefix sum. A second tree corrects the overshoot of B1(i)·i, so prefix sums, and with them range sums, come out as B1(i)·i - B2(i) after range updates, all in O(log n). Nesting the loops gives a 2D tree at O(log n · log m) per operation, and a min-tree works only for prefixes and decreasing updates.

You will learn

Support range add with point queries using one Fenwick tree over the difference array
Derive and implement range add with range sum using two trees, prefix(i) = sum(B1, i)·i - sum(B2, i), with 64-bit values and size n + 2
Write a 2D Fenwick tree with nested loops and answer rectangle sums by inclusion-exclusion, knowing its O(log n · log m) cost and n·m memory
Explain when a prefix-min Fenwick tree is valid and why general range minimum with updates needs a segment tree

Chapters

PreviousSparse Table NextDSU Extensions - Painting Offline, Distances and Parity, Arpa's Trick, Small-to-Large