Range Override Logic — அடிப்படை

Range Override Logic — இடைவெளி கேள்விகள்/புதுப்பிப்புகளுக்கான மரக் கட்டமைப்பு.

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

காலத் தொடர், விளையாட்டு தரவு, நேர்காணல் — வேகமான இடைவெளி கேள்விகள்.

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

இடைவெளி [l,r] கேள்வி/புதுப்பிப்பு O(log n); மர உயரம் ≈ log n; 1-அடுக்கு குறியீட்டில் 4n அளவு.

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

# Sketch: range assign + range sum needs assign-lazy with length-aware sum.
# See lazy_propagation_assignment for full pattern.

def range_assign_sum_naive(arr: list[int], l: int, r: int, v: int) -> int:
    for i in range(l, r + 1):
        arr[i] = v
    return sum(arr)


a = [1, 2, 3, 4]
range_assign_sum_naive(a, 1, 2, 7)
print(sum(a))

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

• 0-அடுக்கு/1-அடுக்கு குழப்பம்.
• மர அளவு n மட்டுமல்ல 4n.

முக்கிய பாடங்கள்

• கையெழுது சிறு உதாரணம் வரை.
• புள்ளி புதுப்பிப்பு முதல், பின் வரம்பு.