Prefix Sum Applications (Advanced Usage) — முன்னொட்டுக் கூட்டல் — மேம்பட்ட பயன்பாடுகள்

மேம்பட்ட prefix பயன்பாடு — நிலையான அணி மட்டுமல்ல: நிரப்பு (complement), குறிப்பிட்ட கூட்டு உட்கூறு எண்ணிக்கை, 2D/3D, offline வினாக்கள் map உடன்.

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

மோசடி கண்காணிப்பு — வணிகர் மொத்த செலவு; prefix வேறுபாட்டில் திடீர் உச்சம். கிடங்கு பாதை — பாதை prefix நேரம். காலநிலை விலகல் — பகுதி மொத்தம் 2D prefix.

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

அணியை மாற்றி (எ.கா. 0 → -1) prefix மீள்வருகை — சுழி கூட்டு உட்கூறு. அல்லது count[pref] map — இலக்கு கூட்டு T க்கு current-T பார்வை.

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

from collections import defaultdict


def subarrays_with_sum_zero(a: list[int]) -> int:
    pref, cnt, ans = 0, defaultdict(int), 0
    cnt[0] = 1
    for x in a:
        pref += x
        ans += cnt[pref]
        cnt[pref] += 1
    return ans


print(subarrays_with_sum_zero([1, -1, 1, -1]))

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

• mod k வகுப்புகள் கணக்கில் மறத்தல்.
• பெரிய ஓட்டத்தில் map நினைவு வெடிப்பு.
• 1D/2D வார்ப்புரு கலவை.

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

• Prefix — இடைவெளி வினாக்களின் மொழி.
• எண்ணும் பிழைக்கு prefix நேரகோடு வரை.
• பெரிய மதிப்புடன் ஒழுங்கமைப்பு சுருக்கம்.