op = lambda x, y: x + y
tree = {}

def build(node, L, R):
    if L == R:
        tree[node] = xs[L] 
    else:
        mid = (L + R) // 2
        build(2 * node, L, mid) 
        build(2 * node + 1, mid + 1, R)
        tree[node] = op(tree[2 * node], tree[2 * node + 1]) 


def query(node, L, R, qL, qR):
    if qL > qR: 
        return 0
    if qL == L and qR == R:
        return tree[node]
    mid = (L + R) // 2
    left = query(2 * node, L, mid, qL, min(qR, mid))
    right = query(2 * node + 1, mid + 1, R, max(qL, mid + 1), qR)
    return op(left, right)


def update(v, L, R, pos, new_val):
    if L == R:
        tree[v] = new_val
    else:
        mid = (L + R) // 2
        if pos <= mid:
            update(v*2, L, mid, pos, new_val)
        else:
            update(v * 2 + 1, mid + 1, R, pos, new_val)
        tree[v] = tree[v * 2] + tree[v * 2 + 1]



xs = [1,-2,3,4,-5,-4,3,2,1]
ranges = [[1,3,5],[0,4,2],[6,8,1]]
build(1, 0, len(xs) - 1)
print(tree)

_max = float('-inf')
for left, right, new_value in ranges:
    update(1, 0, len(xs) - 1, left, new_value)
    ans = query(1, 0, len(xs) - 1, left, right)
    print(ans)
    _max = max(_max, ans)
print(_max)