Prefixes, Fenwick trees, segment trees and sparse tables

Static prefix sums answer sum(l,r)=P[r]−P[l] in O(1), but an update changes many prefixes. Fenwick trees store low-bit-defined prefix blocks; add and prefix sum cost O(log n), with ranges formed by subtraction.

Segment trees split intervals and store aggregates. Combine must be associative, and an identity represents empty ranges. Lazy propagation postpones range updates in tags; assignment/addition composition order matters. Reading children without propagating pending tags can return stale values.

Sparse tables give O(1) static queries for idempotent operations such as minimum through overlapping blocks. Overlap double-counts sums. Fenwick minimum updates need stronger restrictions than sum updates; not every range/operation combination has the same contract.

Which range structure, and which algebra?

Prefix sums use prefix[i+1]=prefix[i]+a[i], so [l,r) sums equal prefix[r]−prefix[l]. Updating one element changes every later prefix. Fenwick trees use lowbit(i)=i&−i to store power-of-two ranges; updates jump upward and prefix queries downward. Test zero-based public APIs against one-based internal indexing.

Segment-tree merges must be associative. Identities include zero for sum, +∞ for minimum and −∞ for maximum. Commutativity is not required: string concatenation queries must preserve order. Mixing half-open [l,r) and inclusive [l,r] contracts causes boundary errors.

Lazy propagation updates aggregates while deferring tags to children. Range-add/range-sum requires aggregate += delta·length. Combining assignment and addition requires correct composition: assigning then adding differs from adding then assigning.

Foundation: Build prefixes for [2,4,1,7] and sum [1,3). Intermediate: Compare random Fenwick updates and queries against naive sums. Advanced: Define assignment/addition tag algebra and test identity, composition and aggregate-action laws.

class Fenwick:
    def __init__(self, n): self.t = [0]*(n+1)
    def add(self, i, delta):
        if not 0 <= i < len(self.t)-1: raise IndexError(i)
        i += 1
        while i < len(self.t): self.t[i] += delta; i += i & -i
    def prefix(self, end):
        if not 0 <= end <= len(self.t)-1: raise IndexError(end)
        s = 0
        while end: s += self.t[end]; end -= end & -end
        return s
f = Fenwick(4)
for i,x in enumerate([2,1,3,4]): f.add(i,x)
assert f.prefix(3)-f.prefix(1) == 4