Segment Trees & BIT — Master Recap & Cheatsheet

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

    def update(self, i, delta):
        # i is 1-indexed
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)

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

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

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

    def update(self, node, start, end, idx, val):
        if start == end:
            self.tree[node] = val; return
        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
        if l <= start and end <= r: return self.tree[node]
        mid = (start + end) // 2
        return self.query(2*node, start, mid, l, r) +                self.query(2*node+1, mid+1, end, l, r)

class BIT2D:
    def __init__(self, m, n):
        self.m, self.n = m, n
        self.tree = [[0]*(n+1) for _ in range(m+1)]

    def update(self, r, c, delta):
        i = r
        while i <= self.m:
            j = c
            while j <= self.n:
                self.tree[i][j] += delta
                j += j & (-j)
            i += i & (-i)

    def query(self, r, c):
        s = 0; i = r
        while i > 0:
            j = c
            while j > 0:
                s += self.tree[i][j]
                j -= j & (-j)
            i -= i & (-i)
        return s

diff = [0] * (n + 1)
# Range add [l, r] += val:
diff[l] += val
diff[r+1] -= val
# Reconstruct:
running = 0
for i in range(n):
    running += diff[i]
    arr[i] += running