Prefix Product Construction

Prefix products accumulate multiplication just like prefix sums accumulate addition. They shine in modular combinatorics, independent-event probabilities, and the classic “product except self” interview puzzle—watch zeros.

Why this shows up in the real world

Growth multipliers compound: multiply per-period factors to get total expansion—prefix products along a timeline answer “how big after k steps?”. Reliability chains multiply survival probabilities. In contests, modulo keeps numbers small; modular inverses let you divide when the modulus is prime and denominators are coprime.

Core idea (explained for students)

Let p[k] be the product of a[0..k], usually with p[-1] = 1 as a conceptual sentinel. Apply % MOD after each multiply when required. If zeros appear, either split segments between zeros or track the last zero index because any range including zero has product zero. For “divide out a[i]”, combine prefix and suffix products in linear time.

Try this in Python

MOD = 1_000_000_007


def prefix_products(a: list[int]) -> list[int]:
    p = 1
    out = []
    for x in a:
        p = p * x % MOD
        out.append(p)
    return out


print(prefix_products([2, 3, 4]))

Common mistakes

• Using Fermat’s little theorem inverse when the denominator shares factors with MOD.
• Letting intermediate products overflow before modulo in languages without big integers.
• Ignoring negative counts of prime factors in factorial-style problems.

Key takeaways

• Prefix + suffix products solve many range product queries offline.
• Always clarify modulus, zeros, negatives before implementing.
• Log-domain tricks turn products into sums—but only for positive bases.