📜 WAYPOINT LESSON
Prefix-Sum Merge Costs
⭐⭐⭐ advanced⏳ 30 min read📍 Lesson 162 of 281
When merging costs depend on the interval's total (stone piles), prefix sums make each transition O(1) after the split loop.
The cost of merging
Stone merging adds the interval SUM at every merge. Precompute prefix sums so any interval's cost is pre[j] - pre[i-1]. The DP structure is identical to matrix-chain; only the merge-cost term changes.