Range Query Processing (prefix, trees) — இடைவெளி கேள்வி

இடைவெளி கேள்வி — தொடர் பகுதி; மரம் / Fenwick / sqrt.

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

காலத் தொடர் — சாளரம். மரபணு — நகரும் சாளரம்.

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

நிலையான கூட்டு — prefix; புதுப்பிப்பு+min — மரம்; lazy — ஒதுக்கீடு.

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

def range_sum_prefix(pref: list[int], l: int, r: int) -> int:
    return pref[r] - pref[l]


pref = [0, 2, 5, 9]
print(range_sum_prefix(pref, 0, 3))

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

• Fenwick min தவறு.
• r எல்லை.

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

• [l,r) ஒருமுறை.
• Mo — offline பல கேள்வி.