1582 articles
Apply many range shift operations to a string in O(n + q) using a difference array. The textbook example of when a diff array beats a segment tree, and the canonical interview signal for offline range updates.
Master LeetCode 304 Range Sum Query 2D Immutable with 2D prefix sums, inclusion-exclusion, and the natural extension to 2D Fenwick tree (BIT) for the mutable variant.
Solve LeetCode 732 My Calendar III using a sweep-line difference array in O(n) per booking, then upgrade to a dynamic lazy segment tree with coordinate compression for O(log n) range updates and max queries.
Crack LeetCode 363 Max Sum of Rectangle No Larger Than K by fixing two row boundaries to collapse 2D into 1D, then using prefix sums plus a sorted set (or BIT/segment tree) to find the best subarray sum bounded above by K.
Find the longest contiguous subarray whose sum is at most K in linear time using prefix sums plus a decreasing monotonic stack, then learn the segment tree and BIT alternatives for streaming variants.