Customer revenue with referral credit and bottom-k query

Build an in-memory system that tracks how much revenue each customer brings in, including revenue from the customers they referred.

Customers get integer ids starting at 0, in the order they are added. A customer may name one existing customer as their referrer. A customer's total revenue is their own revenue plus the own revenue of every customer they referred directly. Credit goes up one level only. If C was referred by B and B by A, C's revenue counts toward B's total but not A's.

Implement a class RevenueSystem:

• add_customer(revenue: int, referrer_id: int | None = None) -> int: adds a customer with an initial revenue (>= 0) and an optional referrer, and returns the new id.
• add_revenue(customer_id: int, amount: int) -> None: records more revenue for an existing customer. It counts toward that customer's total and toward their referrer's total.
• lowest_k(k: int, min_revenue: int) -> list[int]: returns the ids of up to k customers whose total revenue is strictly greater than min_revenue. Order them by total ascending, with ties broken by smaller id.

Inserts, revenue events and queries are interleaved, and there can be up to 10^5 of each. Aim for updates and queries that are much faster than recomputing every total.

Example 1

add_customer(40)        -> 0
add_customer(25, 0)     -> 1    # totals: 0 = 65, 1 = 25
add_customer(60)        -> 2    # totals: 0 = 65, 1 = 25, 2 = 60
lowest_k(2, 30)         -> [2, 0]

Example 2

add_customer(8)         -> 0
add_customer(12, 0)     -> 1
add_customer(3, 1)      -> 2    # 1 = 15, 0 = 20 (2's revenue does not reach 0)
add_revenue(2, 10)      -> 2 = 13, 1 = 25, 0 unchanged at 20
lowest_k(5, 13)         -> [0, 1]

Follow-up (part 2): add nested_revenue(customer_id, max_depth). It returns the customer's own revenue plus the revenue of every customer up to max_depth referral levels below them.

Reconstructed from the reported question; details may differ from what interviewers ask.