Segment Tree & Fenwick Tree

Concept

Prefix sums give O(1) range sums but O(n) updates. Segment and Fenwick trees balance both to O(log n).

A segment tree stores the answer for each segment in a binary tree; a query combines O(log n) nodes. With lazy propagation it also supports range updates.

A Fenwick (Binary Indexed) tree is smaller and simpler: index i stores a partial sum covering i & -i elements. Great for sums and counting inversions.

Complexity

Code (Python)

class Fenwick:
    def __init__(self, n):
        self.t = [0] * (n + 1)
    def add(self, i, delta):         # 1-indexed
        while i < len(self.t):
            self.t[i] += delta
            i += i & -i
    def prefix(self, i):
        s = 0
        while i > 0:
            s += self.t[i]
            i -= i & -i
        return s
    def range_sum(self, l, r):
        return self.prefix(r) - self.prefix(l - 1)

class SegTree:                       # range minimum
    def __init__(self, arr):
        self.n = len(arr)
        self.t = [float("inf")] * (2 * self.n)
        self.t[self.n:] = arr
        for i in range(self.n - 1, 0, -1):
            self.t[i] = min(self.t[2 * i], self.t[2 * i + 1])
    def update(self, i, val):
        i += self.n
        self.t[i] = val
        while i > 1:
            i //= 2
            self.t[i] = min(self.t[2 * i], self.t[2 * i + 1])
    def query(self, l, r):           # [l, r)
        res, l, r = float("inf"), l + self.n, r + self.n
        while l < r:
            if l & 1: res = min(res, self.t[l]); l += 1
            if r & 1: r -= 1; res = min(res, self.t[r])
            l //= 2; r //= 2
        return res

Remember

• Many queries + updates on ranges → segment/Fenwick tree.
• Fenwick for sums/counts; segment tree for min/max/custom merges.
• Coordinate-compress large values first.