Segment Trees & BIT (Fenwick Tree) — Complete Guide

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)  # move to parent

    def query(self, i):  # prefix sum [1..i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)  # move to left sibling
        return s

    def range_query(self, l, r):
        return self.query(r) - self.query(l - 1)

class SegTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (4 * n)

    def build(self, arr, node, start, end):
        if start == end:
            self.tree[node] = arr[start]
        else:
            mid = (start + end) // 2
            self.build(arr, 2*node, start, mid)
            self.build(arr, 2*node+1, mid+1, end)
            self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

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

    def query(self, node, start, end, l, r):
        if r < start or end < l: return 0  # out of range
        if l <= start and end <= r: return self.tree[node]  # complete overlap
        mid = (start + end) // 2
        return self.query(2*node, start, mid, l, r) +                self.query(2*node+1, mid+1, end, l, r)

# Mark pending update at node; push down before querying children
def push_down(self, node, start, end):
    if self.lazy[node] != 0:
        mid = (start + end) // 2
        self.tree[2*node] += self.lazy[node] * (mid - start + 1)
        self.tree[2*node+1] += self.lazy[node] * (end - mid)
        self.lazy[2*node] += self.lazy[node]
        self.lazy[2*node+1] += self.lazy[node]
        self.lazy[node] = 0