K-th Smallest Query — அடிப்படை

K-th Smallest Query — இடைவெளி கேள்விகள்/புதுப்பிப்புகளுக்கான மரக் கட்டமைப்பு.

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

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

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

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

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

def kth_smallest_brute(arr: list[int], l: int, r: int, k: int) -> int:
    return sorted(arr[l : r + 1])[k - 1]


print(kth_smallest_brute([3, 1, 4, 1, 5], 0, 4, 3))

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

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

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

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