386. Bus Route Passenger Count Tracker

Bus Route Passenger Count Tracker

A bus route has several stops. The number of passengers who boarded at each stop is recorded in the order of the stops.

A recorded count may be corrected (updated) . You must also support finding the total number of passengers who boarded across any continuous range of stops.

Class and Methods

RoutePassengerTracker( List<Integer> boardedPassengers )

Initializes the tracker with the passenger count at every stop. Stop indices are zero-based.

void correctStopCount( int stopIndex, int correctedCount )

Replaces the passenger count at stopIndex with correctedCount.

long countPassengers( int firstStop, int lastStop )

Returns the total passenger count from firstStop through lastStop, including both stops.

Rules

A correction replaces the previous count; it does not add to it.
Every query must include all corrections made before it.
The number and order of stops never change.
The same stop may be corrected multiple times.
No parameter value will be null.

Efficiency Requirements

correctStopCount must run in O(log n) time.
countPassengers must run in O(log n) time.

Constraints

1 <= boardedPassengers.size() <= 100,000
0 <= boardedPassengers.get(i) <= 1,000,000,000
0 <= correctedCount <= 1,000,000,000
0 <= stopIndex < boardedPassengers.size()
0 <= firstStop <= lastStop < boardedPassengers.size()
At most 100,000 calls will be made to correctStopCount and countPassengers combined.

Examples

Example 1

RoutePassengerTracker( boardedPassengers = List.of(11, 6, 18, 9, 4) ) countPassengers( firstStop = 1, lastStop = 3 )

Output: 33

The total is 6 + 18 + 9 = 33.

correctStopCount( stopIndex = 2, correctedCount = 13 )

The recorded counts become [11,6,13,9,4].

countPassengers( firstStop = 0, lastStop = 2 )

Output: 30

The updated total is 11 + 6 + 13 = 30.

Example 2

RoutePassengerTracker( boardedPassengers = List.of(3, 0, 7, 5) ) countPassengers( firstStop = 0, lastStop = 3 )

Output: 15

correctStopCount( stopIndex = 1, correctedCount = 8 ) countPassengers( firstStop = 1, lastStop = 2 )

Output: 15

The passenger counts at stops 1 and 2 are now 8 and 7.

Example 3

RoutePassengerTracker( boardedPassengers = List.of(20) ) countPassengers( firstStop = 0, lastStop = 0 )

Output: 20

correctStopCount( stopIndex = 0, correctedCount = 2 ) countPassengers( firstStop = 0, lastStop = 0 )

Output: 2