Fast Queries (Optimizing Multiple Queries) — விரைவு கேள்விகள்

விரைவு கேள்வி — முன் செயலாக்கம்; prefix / segment tree.

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

வரைபடம் — pyramid. அளவீடு — முன் கூட்டு.

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

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

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

def build_prefix(a: list[int]) -> list[int]:
    p = [0]
    for x in a:
        p.append(p[-1] + x)
    return p


def range_sum(p: list[int], l: int, r: int) -> int:
    return p[r + 1] - p[l]


p = build_prefix([3, 1, 4, 1, 5])
print(range_sum(p, 1, 3))

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

• ஒரே கேள்விக்கு பெரிய மரம்.
• prefix எல்லை.

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

• கட்டுமான்+கேள்வி எதிர் brute.
• index மாண்பிம்பு.