Fixed-Size Window Sums
Slide a window of length k in O(n).
The Repeated-Sum Problem
Many tasks ask for the sum of every block of k consecutive elements. Recomputing each block from scratch is wasteful, and you can do better. 🪟
The Slow Way First
The naive idea adds up each window of length k separately. That repeats work and costs O(n times k), which is too slow for large inputs.
for i in range(n - k + 1):
s = sum(a[i:i + k])