Efficient Range Updates Using Difference Array — வேறுபாட்டு அணி — இடைவெளி புதுப்பிப்பு

வேறுபாட்டு அணி பல இடைவெளி கூட்டல்களை ஒவ்வொரு index-க்கும் தனியாகச் செய்யாமல், எல்லைகளில் மட்டும் குறி செய்து, இறுதியில் ஒரு prefix கடந்து முடிவு அணியை O(n) நேரத்தில் கட்டமைக்க உதவுகிறது.

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

நெடுஞ்சாலை தாமதம் — தொடர்ச்சியான பகுதிகளில் +1: ஒவ்வொரு கி.மீ. தனியாக வரையாமல், தொடக்கத்தில் +1, முடிவுக்குப் பிறகு -1; ஓடும் கூட்டல் முழு பாதையையும் காட்டும். விடுமுறை ஹோட்டல் விலை, மணி வாள் விளம்பர எண்ணிக்கை, வகுப்பறை இருக்கை முன்பதிவு — ஒரே முறை.

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

diff நீளம் n (அல்லது R+1 பாதுகாப்புக்கு n+1). [L,R] இல் v கூட்ட: diff[L]+=v, R+1<n எனில் diff[R+1]-=v. பின் iக்கு running+=diff[i] — இது முடிவு. 2D — செவ்வக எல்லைகள்.

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

def apply_range_adds(n: int, updates: list[tuple[int, int, int]]) -> list[int]:
    """updates: (L, R, v) inclusive, 0-based indices"""
    diff = [0] * (n + 1)
    for L, R, v in updates:
        diff[L] += v
        diff[R + 1] -= v
    out, s = [], 0
    for i in range(n):
        s += diff[i]
        out.append(s)
    return out


# +5 on [1..3], +2 on [2..4] over indices 0..5
print(apply_range_adds(6, [(1, 3, 5), (2, 4, 2)]))

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

• R+1 இருக்கும்போது - மறத்தல் — வலது பக்கம் “கசிவு”.
• 0/1-அடிப்படை index குழப்பம்.
• இடைப்பட்ட புள்ளி வினாக்கள் — மீண்டும் கட்ட முடியாவிட்டால் Fenwick/segment tree.

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

• ஒரு range-க்கு O(1) குறி; இறுதி O(n).
• வேறுபாடு + prefix — கோட்டில் +v/-v வரை.
• புதுப்பிப்புகள் தொகுக்கப்பட்டால் சிறந்தது.