Prefix Sum - படிப்படியாக புரிந்துகொள்வோம்

Prefix Sum ஏன் தேவையாகிறது?

இந்த array-ஐ பாருங்கள்:

nums = [2, 5, 3, 1]

கேள்வி: Index 1 முதல் 3 வரை உள்ள values-ன் sum என்ன?

சாதாரண முறை:

s = 0
for i in range(1, 4):
    s += nums[i]

Output: 5 + 3 + 1 = 9

இது சரி.

ஆனால்:

• இப்படிப்பட்ட கேள்வி 1000 முறை வந்தால்?
• ஒவ்வொரு முறை loop ஓட வேண்டுமா?

இதுதான் பிரச்சினை.

Prefix Sum என்ன?

நாம் ஒரு விஷயத்தை நினைக்க வேண்டும்:

“ஒவ்வொரு முறையும் புதிதாக கணக்கிடாமல், ஒருமுறை கணக்கிட்டு வைத்துக்கொள்ளலாமே?”

அதற்கான முறையே Prefix Sum.

Prefix என்பதன் அர்த்தம்

Prefix என்றால்:

“தொடக்கம் முதல் இங்கு வரை உள்ள மொத்தம்.”

---

Prefix Array உருவாக்குவது

nums = [2, 5, 3, 1]

prefix = [0] * (len(nums) + 1)

for i in range(len(nums)):
    prefix[i + 1] = prefix[i] + nums[i]

print(prefix)

Output:

[0, 2, 7, 10, 11]

---

இதை எப்படி புரிந்துகொள்வது?

Index	அர்த்தம்	Value
prefix[0]	எதுவும் இல்லை	0
prefix[1]	[2] வரை	2
prefix[2]	[2, 5] வரை	7
prefix[3]	[2, 5, 3] வரை	10
prefix[4]	[2, 5, 3, 1] வரை	11

---

மிக முக்கியமான Formula

Index l முதல் r வரை (inclusive, nums-க்கு 0-based):

segment_sum = prefix[r + 1] - prefix[l]

---

உதாரணம்

nums = [2, 5, 3, 1]
prefix = [0, 2, 7, 10, 11]

l = 1
r = 3

print(prefix[r + 1] - prefix[l])

11 − 2 = 9

சரியான பதில்: 5 + 3 + 1 = 9

---

இது எப்படி வேலை செய்கிறது?

நாம் நேரடியாக மீண்டும் மீண்டும் கூட்டவில்லை.

நாம் செய்தது:

• r வரை உள்ள total
• l க்கு முன் வரை உள்ள total-ஐ கழித்தோம்

இதனால் நடுவிலுள்ள values மட்டும் கிடைக்கும்.

---

Time Complexity

• Prefix உருவாக்க → O(n)
• ஒவ்வொரு query → O(1)

அதனால் மிகவும் வேகமாக இருக்கும்.

---

Prefix Sum மற்றும் Subarray

Subarray sum:

sum(l … r) = prefix[r + 1] - prefix[l]

அதனால் prefix sum subarray problems-க்கு மிகவும் முக்கியமானது.

---

Product accumulation - product_accumulation

“ஒருமுறை prefix, பிறகு வேகமான query” என்ற யோசனை கூட்டலுக்குப் பதில் பெருக்கல்-க்கும் பொருந்தும்.

Prefix product array உருவாக்க (1 தொடக்கம் - empty prefix-க்கு neutral):

nums = [2, 5, 3, 4]

pref = [1] * (len(nums) + 1)

for i in range(len(nums)):
    pref[i + 1] = pref[i] * nums[i]

nums-க்கு 0-based, inclusive range l…r product:

segment_product = pref[r + 1] // pref[l]

உதாரணம்

nums = [2, 5, 3, 4]
pref = [1, 2, 10, 30, 120]

l, r = 1, 2  # 5 மற்றும் 3 → product 15
print(pref[r + 1] // pref[l])  # 30 // 2 = 15

முக்கிய குறிப்பு (பூஜ்ஜியம்)

range-இல் 0 இருக்குமானால், division மட்டும் போதாது - பொதுவாக zero count தனியாக track செய்வார்கள். பல கேள்விகள் zeros இல்லாமல் அல்லது modulo மூலம் தருகின்றன.

---

முக்கியமான யோசனை (Complement Concept)

கேள்வி:

“sum = k உள்ள subarrays எத்தனை?”

நாம் இதைப் பயன்படுத்தலாம்:

current_sum - previous_sum = k

அதாவது:

previous_sum = current_sum - k

எளிய உதாரணம்

nums = [1, 2, 3]
k = 3

Subarrays:

• [1, 2] → 3
• [3] → 3

Answer = 2

எப்படி நினைக்க வேண்டும்?

• current sum வைத்துக்கொள்
• (current_sum - k) முன்பே வந்ததா என்று பார்

வந்திருந்தால் → valid subarray

---

Difference Array (அடிப்படை அறிமுகம்)

புதிய பிரச்சினை:

“Index 1 முதல் 3 வரை +5 சேர்க்கவும்.”

சாதாரணமாக: ஒவ்வொரு இடத்திலும் add செய்வோம் (slow)

சரியான யோசனை:

• index 1-ல் +5
• range-க்கு பிறகு (உதாரணம் index 4)-ல் −5

பிறகு prefix பயன்படுத்தி final array உருவாக்கலாம்.

உதாரணம்

diff = [0, 5, 0, 0, -5]

Prefix செய்து final array பெறலாம்.

---

Overlap counting - overlap_counting

சில பிரச்சினைகளில் பல range-கள் (intervals) ஒரு line-இல் இருக்கும் - meeting time போல - and எத்தனை overlap ஆகிறது என்று எண்ண வேண்டும்.

இரண்டு range overlap ஆகுமா?

Inclusive ranges [a1, b1] மற்றும் [a2, b2] overlap ஆகும் என்பதற்கு:

a1 <= b2 மற்றும் a2 <= b1

உதாரணம்: [1, 3] மற்றும் [2, 4] overlap (2 முதல் 3 வரை பொதுவான பகுதி).

Difference + prefix மூலம் பல range-கள்

ஒவ்வொரு range-க்கும் இரண்டு event மட்டும்:

• துவக்கத்தில் +1
• முடிவுக்கு அடுத்த index-இல் -1 (end index உட்பட இன்னும் active)

பிறகு அந்த marks மீது prefix sum ஓடினால், ஒவ்வொரு position-இலும் எத்தனை range active என்று தெரியும். Maximum value → “அதிகபட்ச overlapping meetings” போன்ற கேள்விக்கு பதில்.

# Inclusive ranges [L, R] - சிறிய integer timeline
ranges = [(1, 2), (2, 3), (2, 2)]
M = 6  # R + 1 வரை போதுமான அளவு

diff = [0] * M
for L, R in ranges:
    diff[L] += 1
    if R + 1 < M:
        diff[R + 1] -= 1

active = 0
max_overlap = 0
for x in diff:
    active += x
    max_overlap = max(max_overlap, active)

print(max_overlap)  # 3

இது மேலே உள்ள difference array யோசனையுடன் ஒன்றே: boundary-ஐ ஒருமுறை mark செய்து, ஒரு pass-இல் overlap படித்தல்.

---

பொதுவான தவறுகள்

• prefix index தவறாக பயன்படுத்துவது
• n + 1 size மறந்து விடுவது
• formula-வில் off-by-one பிழை
• தேவையில்லாமல் loop பயன்படுத்துவது

---

பயிற்சி

• [4, -1, 2, 3] க்கு prefix உருவாக்கவும்
• index 1 முதல் 3 வரை sum கண்டுபிடிக்கவும்
• sum = 5 உள்ள subarrays எண்ணிக்கை
• prefix[r + 1] - prefix[l] ஏன் வேலை செய்கிறது என்று விளக்கவும்
• Time range-கள் கொடுக்கப்பட்டால், +1 / -1 mark + prefix pass மூலம் maximum overlap கண்டுபிடிக்க
• Prefix product கட்டி range product query-ஐ O(1)-இல் பதில் (0 இருந்தால் கவனம்)

---

இறுதி புரிதல்

Prefix sum:

• ஒரு preprocessing technique
• repeated calculation-ஐ தவிர்க்க உதவும்

முக்கிய பயன்பாடு:

• range sum
• range product (product accumulation)
• subarray problems
• counting (timeline-இல் overlap counting உட்பட)