Referral Credit Tracker with Indirect Referrals

Build a referral credit tracker. Creating an account gives it an initial credit amount. If it names a referrer, that existing referrer receives the same amount. Support queries selecting up to k accounts whose current total credit meets a threshold. In indirect mode, each ancestor in the referral chain also receives credit.

Implement track_referrals(operations: string[][], include_indirect: bool) -> string[][]. This practice interface uses only string rows:

• ["add", credit, referrer] creates the next account ID and returns a one-element row containing that ID as a decimal string. referrer is an existing ID or "-1" for no referrer.
• ["query", k, threshold] returns a row of qualifying account IDs, encoded as decimal strings, in the order defined below.
• Every numeric input string is a valid decimal integer. There is one output row per input operation, including an empty row when a query selects no accounts.

Constraints & Assumptions

• IDs are assigned as 0, 1, 2, ... in creation order. Accounts are never removed or reparented.
• Credit is between 0 and 1,000,000,000. There are at most 2,000 operations. Threshold is between 0 and 2,000,000,000,000; k is between 0 and 2,000. Use 64-bit totals in fixed-width languages.
• Every account starts with its own initial credit. In direct mode, only its immediate referrer gets an additional copy. In indirect mode, every ancestor gets one copy of the new account's original initial credit.
• Crediting a referrer does not create another referral event. Each new account is processed once.
• For this practice version, a total meets the threshold when it is at least the threshold. Order qualifying accounts by (total_credit, account_id) ascending, and return the first k. Return fewer if insufficient accounts qualify.
• Threshold inclusivity, ordering, ID assignment, and serialization are explicit practice conventions for details not fixed by the report.

Examples

operations = [["add","10","-1"],["add","5","0"],["add","7","1"],["query","2","10"]]
include_indirect = false
result = [["0"],["1"],["2"],["1","0"]]

Final totals are 15, 12, and 7, so accounts 1 and 0 qualify in ascending total order.

operations = [["add","10","-1"],["add","5","0"],["add","7","1"],["query","2","20"]]
include_indirect = true
result = [["0"],["1"],["2"],["0"]]

Indirect propagation makes the totals 22, 12, and 7. The same final query in direct mode would return an empty row.

Hint: Track the source of each credit

Identify the recipients of the new account's original credit before changing totals. Do not propagate a referrer's accumulated total.

Track Referral Credits and Select Accounts by Total

Approach

Keep parallel arrays of total credit and parent ID in creation order. On add, initialize the new total with its original credit and walk the parent chain, adding exactly that original amount to each recipient. Stop after the first parent in direct mode; continue to -1 in indirect mode. Since every parent existed before its child, parent IDs strictly decrease along a chain, so propagation terminates and credits each ancestor once. Never propagate an accumulated total or generate another event from a credit update. By induction after every add, each total is precisely its own initial credit plus the permitted original credits of referred accounts. A query filters with total >= threshold, sorts by numeric total then numeric ID, and takes at most k accounts. Produce a fresh string row for each operation. With N current accounts, add costs O(1) in direct mode or O(H) in indirect mode for chain height H; a query costs O(N log N). Use 64-bit integers in Java and C++; JavaScript numbers exactly represent the bounded totals, which do not exceed 2 trillion.

• Time complexity: Add: O(1) direct or O(H) indirect; query: O(N log N); at most O(M^2 log M) over M operations.
• Space complexity: O(N) working storage plus returned rows.