Prefix Sum on Transformed Array

Sometimes the raw input is not yet “summable.” Transform first—sign flips, logs (careful!), indicator bits, cumulative XOR paired with frequency tricks—then take prefix sums on the new sequence.

Why this shows up in the real world

Bank debits/credits become one signed stream before cumulative balance. Survey Likert scores might be centered (subtract neutral) so prefix tracks “net sentiment drift.” Packet loss flags (0/1) become “how many failures so far” via prefix of the bitstream.

Core idea (explained for students)

Example: turn ( into +1 and ) into -1 for bracket balance; prefix dropping below zero signals invalidity. Another: replace values with 1 if condition holds else 0, then prefix counts how many times the condition was true up to each index. Always document the inverse transform if you need to recover originals.

Try this in Python

def bracket_depths(s: str) -> list[int]:
    delta = {"(": 1, ")": -1}
    pref, cur = [], 0
    for ch in s:
        cur += delta.get(ch, 0)
        pref.append(cur)
    return pref


print(bracket_depths("(()())"))

Common mistakes

• Non-invertible transforms (hashing) when you later need exact reconstruction.
• Log transform with zeros or negatives—handle with offsets or skip logs.
• Overflow when encoding large multipliers into integers during transformation.

Key takeaways

• Ask: “What linear statistic do I need after a cheap per-element map?”
• Validate transforms on two-line examples.
• Keep a legend mapping symbols to numbers in comments.