DSAhardArrays~45m

The Invoice

Problem

You are the backend engineer at a early-stage SaaS startup. Your billing system tracks API usage across n time slots. As the product grows, your naive O(n) implementation is melting under load — invoices are taking seconds to compute and customers are complaining.

You need to rebuild the usage tracker to support three operations efficiently:

("update", i, delta): A customer made delta API calls in time slot i. Add to their running total.
("query", l, r): Generate an invoice line item — return total API calls across slots l to r.
("threshold", k): Find the earliest time slot where cumulative usage first reaches k calls — used to detect when a customer hits their quota. Return -1 if quota is never reached.

All three operations must run in O(log n) time.

Examples

Example 1

Input: (5, [["update",1,10],["update",5,20],["query",1,5]])

Output: [null, null, 30]

After updating slots 1 and 5, querying the full range returns 10+20=30.

Example 2

Input: (4, [["update",1,5],["update",2,5],["threshold",10]])

Output: [null, null, 2]

Prefix sums: slot 1=5, slot 2=10. First slot where prefix sum ≥ 10 is slot 2.

Example 3

Input: (4, [["update",2,10],["query",1,3],["update",3,20],["threshold",25]])

Output: [null, 10, null, 3]

After first update query returns 10. After second update prefix at slot 3 is 30 ≥ 25, so threshold returns 3.

Constraints

›1 <= n <= 10^5
›1 <= i <= n
›1 <= delta <= 10^4
›At most 10^4 operations

Loading question…