a nonrecursive segment tree implementation with range query and single element update works virtually with any list of the same type of elements with a commutative combiner explanation https www geeksforgeeks orgiterativesegmenttreerangeminimumquery https www geeksforgeeks orgsegmenttreeefficientimplementation segmenttree1 2 3 lambda a b a b query0 2 6 segmenttree3 1 2 min query0 2 1 segmenttree2 3 1 max query0 2 3 st segmenttree1 5 7 1 6 lambda a b a b st update1 1 st update2 3 st query1 2 2 st query1 1 1 st update4 1 st query3 4 0 st segmenttree1 2 3 3 2 1 1 1 1 lambda a b ai bi for i in rangelena st query0 1 4 4 4 st query1 2 4 3 2 st update1 1 1 1 st query1 2 0 0 0 st query0 2 1 2 3 segment tree constructor it works just with commutative combiner param arr list of elements for the segment tree param fnc commutative function for combine two elements segmenttree a b c lambda a b f ab query0 2 abc segmenttree1 2 2 3 3 4 lambda a b a0 b0 a1 b1 query0 2 6 9 update an element in logn time param p position to be update param v new value st segmenttree3 1 2 4 min st query0 3 1 st update2 1 st query0 3 1 get range query value in logn time param l left element index param r right element index return element combined in the range l r st segmenttree1 2 3 4 lambda a b a b st query0 2 6 st query1 2 5 st query0 3 10 st query2 3 7 test all possible segments segment tree constructor it works just with commutative combiner param arr list of elements for the segment tree param fnc commutative function for combine two elements segmenttree a b c lambda a b f a b query 0 2 abc segmenttree 1 2 2 3 3 4 lambda a b a 0 b 0 a 1 b 1 query 0 2 6 9 update an element in log n time param p position to be update param v new value st segmenttree 3 1 2 4 min st query 0 3 1 st update 2 1 st query 0 3 1 noqa e741 get range query value in log n time param l left element index param r right element index return element combined in the range l r st segmenttree 1 2 3 4 lambda a b a b st query 0 2 6 st query 1 2 5 st query 0 3 10 st query 2 3 7 test all possible segments
from __future__ import annotations

from collections.abc import Callable
from typing import Any, Generic, TypeVar

T = TypeVar("T")


class SegmentTree(Generic[T]):
    def __init__(self, arr: list[T], fnc: Callable[[T, T], T]) -> None:
        
        any_type: Any | T = None

        self.N: int = len(arr)
        self.st: list[T] = [any_type for _ in range(self.N)] + arr
        self.fn = fnc
        self.build()

    def build(self) -> None:
        for p in range(self.N - 1, 0, -1):
            self.st[p] = self.fn(self.st[p * 2], self.st[p * 2 + 1])

    def update(self, p: int, v: T) -> None:
        
        p += self.N
        self.st[p] = v
        while p > 1:
            p = p // 2
            self.st[p] = self.fn(self.st[p * 2], self.st[p * 2 + 1])

    def query(self, l: int, r: int) -> T | None:  
        
        l, r = l + self.N, r + self.N

        res: T | None = None
        while l <= r:
            if l % 2 == 1:
                res = self.st[l] if res is None else self.fn(res, self.st[l])
            if r % 2 == 0:
                res = self.st[r] if res is None else self.fn(res, self.st[r])
            l, r = (l + 1) // 2, (r - 1) // 2
        return res


if __name__ == "__main__":
    from functools import reduce

    test_array = [1, 10, -2, 9, -3, 8, 4, -7, 5, 6, 11, -12]

    test_updates = {
        0: 7,
        1: 2,
        2: 6,
        3: -14,
        4: 5,
        5: 4,
        6: 7,
        7: -10,
        8: 9,
        9: 10,
        10: 12,
        11: 1,
    }

    min_segment_tree = SegmentTree(test_array, min)
    max_segment_tree = SegmentTree(test_array, max)
    sum_segment_tree = SegmentTree(test_array, lambda a, b: a + b)

    def test_all_segments() -> None:
        
        for i in range(len(test_array)):
            for j in range(i, len(test_array)):
                min_range = reduce(min, test_array[i : j + 1])
                max_range = reduce(max, test_array[i : j + 1])
                sum_range = reduce(lambda a, b: a + b, test_array[i : j + 1])
                assert min_range == min_segment_tree.query(i, j)
                assert max_range == max_segment_tree.query(i, j)
                assert sum_range == sum_segment_tree.query(i, j)

    test_all_segments()

    for index, value in test_updates.items():
        test_array[index] = value
        min_segment_tree.update(index, value)
        max_segment_tree.update(index, value)
        sum_segment_tree.update(index, value)
        test_all_segments()