Map Weighted Random Draws to Indices

Problem Statement

You are tasked with building a weighted random sampler. Given an array of positive integers weights, where weights[i] represents the weight of index i, you must process a series of draws (numbers between 1 and the total sum of all weights).

Your goal is to implement a class WeightedSampler that maps each draw to the corresponding index. A draw $x$ maps to index $i$ if the cumulative sum of weights up to index $i-1$ is strictly less than $x$, and the cumulative sum up to index $i$ is greater than or equal to $x$.

Implementation Interface

class WeightedSampler:
    def __init__(self, weights: list[int]):
        # Initialize data structures for efficient lookup
        pass

    def get_index(self, draw: int) -> int:
        # Map the draw to an index (0-indexed)
        pass

Constraints

• `1 <= len(weights) 0 (Range [1, 1])
• get_index(2) -> 1 (Range [2, 4])
• get_index(4) -> 1 (Range [2, 4])
• get_index(6) -> 2 (Range [5, 6])

Edge Cases

• Single element in weights.
• draw values exactly equal to cumulative boundary points.