Implement a Referral Revenue Tracker

Implement an in-memory revenue tracking system for customers in a referral network.

Each customer has their own direct revenue. A customer may also have been referred by another customer. If customer B was referred by customer A, then A's aggregate revenue includes both A's own direct revenue and all revenue generated by B. Assume this relationship is recursive, so a customer's aggregate revenue includes the revenue of all customers in their referral subtree.

Design a data structure with these operations:

1. insert_revenue(customer_id, amount, referrer_id=None)

   • Add amount to the direct revenue of customer_id.
   • If the customer does not already exist, create them.
   • If referrer_id is provided when the customer is first created, link the customer under that referrer.
   • You may assume there are no referral cycles, and any provided referrer already exists.

2. top_k_above(k, threshold)

   • Return the top k customers whose aggregate revenue is strictly greater than threshold.
   • Sort results by aggregate revenue in descending order. Break ties by customer ID.

Discuss your design choices and implement the required methods efficiently.

Implement a Referral Revenue Tracker

You are given a sequence of operations for an in-memory referral revenue tracker. Each customer has direct revenue and may have exactly one referrer, forming a forest. A customer's aggregate revenue is the sum of its own direct revenue and the direct revenue of every customer in its referral subtree. Implement the tracker and return the answer for every top_k query. Each operation is one of: ("insert", customer_id, amount, referrer_id): add amount to the direct revenue of customer_id. If the customer does not exist, create it and set its referrer to referrer_id (which may be None). If the customer already exists, ignore the provided referrer_id and only add the revenue. ("top_k", k, threshold): find the customers whose aggregate revenue is strictly greater than threshold, sort them by aggregate revenue descending and then by customer_id ascending, and return the first k as [customer_id, aggregate_revenue] pairs. Return a list containing the result of each top_k query in order.

Constraints

• 0 <= len(operations) <= 10^4
• There are at most 5000 distinct customers
• 1 <= customer_id <= 10^9
• -10^9 <= amount, threshold <= 10^9
• 0 <= k <= number of current customers
• If a new customer is inserted with a non-None referrer_id, that referrer already exists and the referral graph is acyclic

Examples

Example 1

Input: [("insert", 1, 100, None), ("insert", 2, 50, 1), ("insert", 3, 70, 1), ("top_k", 2, 100), ("insert", 2, 30, None), ("top_k", 3, 60)]
Output: [[[1, 220]], [[1, 250], [2, 80], [3, 70]]]

Explanation: After the first three inserts, customer 1 has aggregate revenue 220. After adding 30 more to customer 2, customer 2 becomes 80 and customer 1 becomes 250.

Example 2

Input: [("insert", 1, 50, None), ("insert", 2, 50, None), ("insert", 3, 10, 1), ("insert", 4, 10, 2), ("top_k", 2, 59), ("top_k", 3, 50)]
Output: [[[1, 60], [2, 60]], [[1, 60], [2, 60]]]

Explanation: Customers 1 and 2 both have aggregate revenue 60, so the tie is broken by smaller customer ID first.

Hints

1. When revenue is added to one customer, the same delta must also be reflected in every ancestor's aggregate revenue.
2. For each top_k query, first filter customers whose aggregate revenue is above the threshold, then sort by the required key: descending aggregate revenue and ascending customer ID.