Design and Implement a Concurrent Tally Service

Problem: Design and Implement a Concurrent Tally Service Implement a TallyService that records event occurrences and returns the number of events within a time range. API bump(timestamp: int) -> None query(startTime: int, endTime: int) -> int bump(timestamp) records one event at timestamp. query(startTime, endTime) returns the total number of events in the inclusive range [startTime, endTime]. Requirements Timestamps are integer seconds. Multiple bump calls may occur during the same second. Query ranges are inclusive: events at both startTime and endTime must be included. Calls may arrive out of order. For example, an event at timestamp 95 may be recorded after one at timestamp 100. The service retains only the latest retention seconds of data. Let max_seen_timestamp be the maximum timestamp observed by the service: Events earlier than max_seen_timestamp - retention + 1 may be discarded. A query range must be fully inside the current retention window; otherwise, raise an exception. Implement a thread-safe version with expected complexity: bump: O(log n); query: O(log n); where n is the number of distinct timestamps in the active window. Explain how to further reduce lock contention in a highly concurrent production system and how fixed-size buckets can bound memory usage. CLI Test Format The first line is retention. Each remaining line is one operation until EOF: B timestamp Q startTime endTime B timestamp calls bump(timestamp) and prints nothing. Q startTime endTime calls query(startTime, endTime) and prints its result. Example Input: 10 B 100 B 100 B 103 B 105 Q 100 103 Q 101 104 Output: 3 1 Constraints At most 2 * 10^5 operations. Timestamps are signed 64-bit integers. retention <= 10^9. Example Input 10 B 100 B 100 B 103 B 105 Q 100 103 Q 101 104 Output 3 1