Query Optimization Using Precomputation (tables + lookup) — முன் கணிப்புடன் கேள்வி மேம்பாடு

முன் கணிப்பு + கேள்வி — LCA lift; hash prefix; sparse RMQ.

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

GIS — tile. கம்பைலர் — dominance.

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

table[k][i]; O(log n) துண்டு இணைப்பு.

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

def prefix_mins(a: list[int]) -> list[int]:
    m = []
    cur = None
    for x in a:
        cur = x if cur is None else min(cur, x)
        m.append(cur)
    return m


print(prefix_mins([3, 1, 4, 1, 5]))

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

• நினைவு வெடிப்பு.
• 0/1 அடிப்படை குழப்பம்.

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

• monoid இணைப்பு சரி.
• சிறு n brute சரிபார்ப்பு.