Prefix Sum (Cumulative Sum Technique) — முன்னொட்டுக் கூட்டல் — தொடர் மொத்தம்

Prefix sum அணி pref — தொடர்ச்சி மொத்தங்கள்; இடைவெளி கூட்டல் இரண்டு பார்வைகள்: pref[R]-pref[L-1] (index கவனம்) — அணிகள்/சரங்களில் மிகப் பயன்படும்.

உண்மை உலகில் இது ஏன் முக்கியம்?

பணப்பாய்வு பதிவேடு — “இதுவரை இருப்பு”; ஏப்ரல்–ஜூன் இடைவெளி மீண்டும் நாள் நாள் ஸ்கேன் இல்லாமல். பட integral — வடிகட்டி வேகம். மரபணு ஆழம் — இடைவெளி அறிக்கை.

மையக் கருத்து (மாணவர்களுக்கான விளக்கம்)

prefWith0[0]=0, prefWith0[i+1]=prefWith0[i]+a[i] என [L,R] கூட்டல் prefWith0[R+1]-prefWith0[L]. 2D prefix — செவ்வக கூட்டல்.

Pythonில் முயற்சி செய்வோம்

def range_sums(a: list[int], queries: list[tuple[int, int]]) -> list[int]:
    ps = [0]
    for x in a:
        ps.append(ps[-1] + x)
    return [ps[r + 1] - ps[l] for l, r in queries]


print(range_sums([1, 2, 3, 4, 5], [(1, 3), (0, 4)]))

அடிக்கடி நேரும் தவறுகள்

• L=0 ஒற்றைப் பிழை — பூஜ்ஜிய நீட்டிப்பு.
• mod கழிப்பு — + MOD.
• மாறும் அணியில் prefix மீண்டும் கணிக்காமை.

முக்கியச் சுருக்கக் குறிப்புகள்

• O(n) தயாரிப்பு பின் இடைவெளி O(1).
• prefix → index வரைபடம் — குறிப்பிட்ட கூட்டு துணைஅணி.
• பூஜ்ஜிய நீட்டிப்பு வார்ப்புரு.