Segment trees

The idea

If you need to find the sum of elements from index L to R, you can loop over them in O(N). If you need to update an element, it takes O(1). But if you have millions of queries and updates, O(N) queries are too slow.

A Segment Tree builds a binary tree over the array. The leaves are the array elements. Each parent stores the sum (or min/max) of its two children. To query a range, you combine at most O(log N) pre-computed tree nodes. To update an element, you only update its O(log N) parents.

How it works (Point Update)

def update(node, start, end, idx, val):
    if start == end:
        tree[node] = val
        return
        
    mid = (start + end) // 2
    if start <= idx <= mid:
        update(2 * node, start, mid, idx, val)
    else:
        update(2 * node + 1, mid + 1, end, idx, val)
        
    tree[node] = tree[2 * node] + tree[2 * node + 1]