Persistent Segment Tree — அடிப்படை

Persistent Segment Tree — இடைவெளி கேள்விகள்/புதுப்பிப்புகளுக்கான மரக் கட்டமைப்பு.

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

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

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

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

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

from bisect import bisect_left


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


print(kth_in_sorted_sub([3, 1, 4, 2], 0, 3, 2))

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

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

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

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