Alice takes exams over time and wants a system that can record her scores and answer questions about the total score within any given time range.

We need to implement a class called ExamTracker that supports three operations:

• ExamTracker(): Creates and initializes the tracker object.
• record(time, score): Records that Alice took an exam at time time and scored score points.
• totalScore(startTime, endTime): Returns the sum of scores of all exams Alice took between startTime and endTime, inclusive of both endpoints. If no exams fall within this interval, the answer is 0.

There are two important guarantees that make the problem easier:

1. Records arrive in order: Every call to record() uses a time value that is strictly larger than all previous ones. This means the recorded times naturally form a sorted (increasing) sequence — no sorting is ever needed.
2. No queries about the future: Whenever totalScore(startTime, endTime) is called, the condition startTime <= endTime <= t holds, where t is the latest recorded time. In other words, queries only ask about time ranges that are already fully covered by the existing records.

For example, if Alice records:

• record(1, 98) — score 98 at time 1
• record(5, 99) — score 99 at time 5

Then:

• totalScore(1, 3) returns 98, because only the exam at time 1 falls in the range [1, 3].
• totalScore(1, 5) returns 197, because both exams fall in the range [1, 5].
• totalScore(2, 4) returns 0, because no exam was taken in the range [2, 4].

The main challenge is to make totalScore efficient when there are many records and many queries. Since the times are already sorted, a natural idea is to maintain a prefix sum array alongside the times, so each query can be answered with binary search in O(log n) time instead of scanning all records.

The naive approach would be to store every (time, score) pair in a list, and for each totalScore(startTime, endTime) query, scan through all records and sum up the scores whose times fall inside the range. This works, but every query costs O(n) time, which becomes slow when there are many records and many queries.

To do better, let's look at what the problem gives us for free:

1. The times are already sorted. Since record() is always called with strictly increasing time, the list of recorded times is naturally in ascending order without any extra work.
2. A range-sum query on a sorted timeline is really an interval sum. The exams inside [startTime, endTime] form a contiguous block in our list, because the times are sorted. So the question "what is the total score in this time range?" reduces to "what is the sum of a contiguous segment of the score list?"

These two observations point directly to two classic tools:

• Prefix sums answer "sum of a contiguous segment" in O(1). If pre[i] is the total score of the first i exams, then the sum of exams from index l+1 to r is simply pre[r] - pre[l].
• Binary search finds the boundaries of that segment in O(log n). On the sorted times array, we can binary search for the first exam with time >= startTime and the last exam with time <= endTime.

Putting it together: maintain times and pre side by side. Each record() just appends to both arrays — appending a new time keeps times sorted, and appending pre[-1] + score extends the running total, both in O(1). Each totalScore() does two binary searches to locate the segment boundaries, then one subtraction of prefix sums.

One small but elegant trick: we initialize both arrays with a sentinel 0 (times = [0], pre = [0]). This sentinel acts as a "virtual exam at time 0 with score 0", which removes the need for special-case handling when the binary search lands before the first real record — the index -1 situation simply never occurs, and an empty range naturally yields pre[r] - pre[l] = 0.

This way, recording stays O(1) and querying drops from O(n) to O(log n).

Pattern Learn more about Binary Search and Prefix Sum patterns.

We follow the Prefix Sum + Binary Search strategy, maintaining two parallel arrays that grow together as exams are recorded.

Data Structures

• times: a sorted list of exam times, initialized as [0] (a sentinel).
• pre: a prefix sum list, where pre[i] is the total score of the first i exams, initialized as [0].

The sentinel pair (times[0] = 0, pre[0] = 0) represents a virtual exam at time 0 with score 0. It guarantees that any binary search result minus one is still a valid index, so no edge-case checks are needed.

record(time, score) — O(1)

def record(self, time: int, score: int) -> None:
    self.times.append(time)
    self.pre.append(self.pre[-1] + score)

Two steps happen here:

1. Append time to times. Because calls arrive with strictly increasing time, the array stays sorted automatically.
2. Append pre[-1] + score to pre, extending the running total so that pre[i] - pre[j] always equals the sum of scores of exams j+1 through i.

totalScore(startTime, endTime) — O(log n)

def totalScore(self, startTime: int, endTime: int) -> int:
    l = bisect_left(self.times, startTime) - 1
    r = bisect_left(self.times, endTime + 1) - 1
    return self.pre[r] - self.pre[l]

We need the sum of exams whose times lie in [startTime, endTime]. Two binary searches locate the boundaries of this contiguous block:

1. Left boundary: bisect_left(times, startTime) returns the index of the first exam with time >= startTime. Subtracting 1 gives l, the index of the last exam strictly before startTime. Everything up to l must be excluded.
2. Right boundary: bisect_left(times, endTime + 1) returns the index of the first exam with time > endTime. Subtracting 1 gives r, the index of the last exam with time <= endTime. Everything up to r must be included.
3. Answer: the exams in the range are exactly those at indices l+1 through r, so the result is pre[r] - pre[l].

Example Walkthrough

Suppose Alice calls:

Now query totalScore(1, 3):

• l = bisect_left(times, 1) - 1 = 1 - 1 = 0
• r = bisect_left(times, 4) - 1 = 2 - 1 = 1
• Answer: pre[1] - pre[0] = 98 - 0 = 98 ✓

Query totalScore(2, 4) (empty range):

• l = bisect_left(times, 2) - 1 = 2 - 1 = 1
• r = bisect_left(times, 5) - 1 = 2 - 1 = 1
• Answer: pre[1] - pre[1] = 0 ✓ — when no exam falls in the interval, l and r coincide and the subtraction naturally yields 0.

Complexity Analysis

• Time: record is O(1) amortized (a single append to each array); totalScore is O(log n) due to the two binary searches, where n is the number of recorded exams.
• Space: O(n) to store the two arrays.

Alternative Perspectives

• Binary Indexed Tree / Segment Tree: These also support point updates and range-sum queries in O(log n). They are more general (e.g., they handle unordered insertions or score modifications), but here they are unnecessary overhead since times arrive pre-sorted and scores never change.
• Sliding-window pruning: If queries were known to only touch recent times, old records could be discarded to save memory. The problem gives no such guarantee, so we keep the full history.

The prefix sum + binary search combination is the cleanest fit: it exploits the chronological-order guarantee to get constant-time updates and logarithmic-time queries with minimal code.