segment-tree

Segmentlar daraxti — massivda ikki xil amalni O(log n) da bajaradi: elementni o‘zgartirish va oraliq bo‘yicha so‘rov (yig‘indi, minimum, maksimum). Prefiks yig‘indi faqat o‘zgarmas massivda ishlaydi; o‘zgarishlar bo‘lsa — segmentlar daraxti.

size = 1
while size < n:
    size *= 2
t = [float("inf")] * (2 * size)
t[size:size + n] = a
for i in range(size - 1, 0, -1):
    t[i] = min(t[2 * i], t[2 * i + 1])

def update(i, x):
    i += size; t[i] = x
    while i > 1:
        i //= 2
        t[i] = min(t[2 * i], t[2 * i + 1])

def query(l, r):                 # [l, r)
    res, l, r = float("inf"), l + size, r + size
    while l < r:
        if l & 1: res = min(res, t[l]); l += 1
        if r & 1: r -= 1; res = min(res, t[r])
        l //= 2; r //= 2
    return res

Faqat yig‘indi va nuqtali o‘zgarish kerak bo‘lsa, qisqaroq Fenwick daraxti ham yetadi.