Design a Customer Revenue Index with Referrals and Threshold Queries

Problem Statement

Design an in-memory revenue tracking system, CustomerRevenueTracker, that monitors customer revenue including referral bonuses and supports range-based threshold queries.

Each customer can have an optional direct referrer. When a customer earns direct revenue, both that customer's total revenue and their direct referrer's total revenue (if one exists) increase by that amount. Referral credits do not propagate beyond one level (i.e., strictly direct referrals).

You need to implement the CustomerRevenueTracker class with the following methods:

• __init__(): Initializes the data structure.
• register_customer(customer_id: int, referrer_id: int | None) -> None: Registers a new customer with an optional existing referrer. A customer ID is guaranteed to be unique and never registered more than once. If referrer_id is provided, it is guaranteed that referrer_id has already been registered. Initial revenue for a new customer is 0.
• add_revenue(customer_id: int, amount: int) -> None: Adds amount (amount > 0) to customer_id's direct revenue. This also credits the same amount to their direct referrer's total revenue (if they have one).
• get_lowest_revenue_above(threshold: int) -> int | None: Returns the customer_id of the customer whose total revenue is greater than or equal to threshold, and has the lowest total revenue among all such customers. If multiple customers tie for the lowest total revenue above or equal to threshold, return the customer with the smallest customer_id. If no customer meets the threshold, return None.

Example

tracker = CustomerRevenueTracker()
tracker.register_customer(1, None)  # Customer 1 has no referrer
tracker.register_customer(2, 1)     # Customer 2 referred by 1
tracker.register_customer(3, 1)     # Customer 3 referred by 1

tracker.add_revenue(2, 50)
# Customer 2 direct: 50, total: 50
# Customer 1 referral: 50, direct: 0, total: 50
# Customer 3 total: 0

tracker.add_revenue(3, 30)
# Customer 3 direct: 30, total: 30
# Customer 1 referral: 80, direct: 0, total: 80

print(tracker.get_lowest_revenue_above(40))
# Customers >= 40 are Customer 2 (50) and Customer 1 (80).
# Lowest total revenue is 50 -> Customer 2.
# Output: 2

print(tracker.get_lowest_revenue_above(50))
# Customer 2 (50) and Customer 1 (80) both >= 50. Lowest is 50 -> Customer 2.
# Output: 2

print(tracker.get_lowest_revenue_above(90))
# Output: None

Constraints

• 1 <= customer_id, referrer_id <= 10^9
• 1 <= amount <= 10^6
• 0 <= threshold <= 10^12
• At most 2 * 10^5 total calls to register_customer, add_revenue, and get_lowest_revenue_above combined.
• Optimal target time complexity:
  • register_customer: O(log N)
  • add_revenue: O(log N)
  • get_lowest_revenue_above: O(log N) where N is the number of registered customers.