Playlist Engagement Tracker
Spotify maintains vast user playlists, and each song within these playlists has an associated "engagement score" (e.g., derived from play counts, skips, or user interactions). To gain deeper insights into user behavior, personalize recommendations, and optimize content, it's crucial to have an efficient system for managing these scores. We need to quickly track individual song engagement and calculate the total engagement for any contiguous sub-segment of a playlist.
Your task is to design and implement a PlaylistEngagementTracker class. This class should efficiently support the following operations:
constructor(initialScores: number[]): Initializes the tracker with an array of initialScores. These scores represent the engagement level of songs in a playlist, where initialScores[i] corresponds to the song at index i.update(index: number, newScore: number): Updates the engagement score of the song at the given index to newScore. This operation modifies the underlying scores.query(left: number, right: number): Returns the sum of engagement scores for all songs in the playlist segment from left to right (inclusive). For example, query(0, 2) would sum scores at indices 0, 1, and 2.constructor(initialScores: number[]):
initialScores: An array of non-negative integers representing the initial engagement scores for songs.void (constructor has no explicit return value).update(index: number, newScore: number):
index: A 0-based integer representing the position of the song to update.newScore: A non-negative integer representing the new engagement score for the song at index.void.query(left: number, right: number):
left: A 0-based integer representing the starting index of the query range (inclusive).right: A 0-based integer representing the ending index of the query range (inclusive).number representing the sum of engagement scores within the specified range.initialScores array) remains constant after the PlaylistEngagementTracker is initialized.index, left, and right parameters for update and query methods will always be valid and within the bounds of the playlist length.Examples
Example 1
Input:
operations = ["PlaylistEngagementTracker","query","update","query","query"], params = [[[1,3,5]],[0,2],[1,2],[0,2],[1,2]]
Output:
[null,9,null,8,7]
Note:
Example 2
Input:
operations = ["PlaylistEngagementTracker","query","update","query"], params = [[[10]],[0,0],[0,5],[0,0]]
Output:
[null,10,null,5]
Note:
Example 3
Input:
operations = ["PlaylistEngagementTracker","update","query","update","query"], params = [[[2,4,6,8]],[0,1],[0,1],[2,7],[0,3]]
Output:
[null,null,5,null,20]
Note:
Constraints
1 <= initialScores.length <= 10^40 <= initialScores[i] <= 10^50 <= newScore <= 10^50 <= index < initialScores.length0 <= left <= right < initialScores.length10^4 calls to update and query combined (after initialization).update and query operations should be significantly better than O(N).update and query operations achieve logarithmic time complexity (O(log N)), and space complexity is appropriate (O(N)).Loading editor...