Segment Trees and BIT — Master Recap and Interview Cheatsheet

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)   # always 1-indexed
 
    def update(self, i, delta):
        while i <= self.n:
            self.tree[i] += delta
            i += i & (-i)   # move to next responsible ancestor
 
    def query(self, i):
        # Returns prefix sum [1..i]
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)   # move to covered left boundary
        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)   # 4*n handles all array sizes safely
        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   # out of range: identity element for sum
        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))

class LazySegTree:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (4 * n)
        self.lazy = [0] * (4 * n)
 
    def _push_down(self, node, start, end):
        if self.lazy[node]:
            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
 
    def range_update(self, node, start, end, l, r, val):
        if r < start or end < l:
            return
        if l <= start and end <= r:
            self.tree[node] += val * (end - start + 1)
            self.lazy[node] += val
            return
        self._push_down(node, start, end)
        mid = (start + end) // 2
        self.range_update(2*node, start, mid, l, r, val)
        self.range_update(2*node+1, mid+1, end, l, r, val)
        self.tree[node] = self.tree[2*node] + self.tree[2*node+1]

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 original:
running = 0
for i in range(n):
    running += diff[i]
    arr[i] += running