Convert a PDF to a CDF

Given a continuous random variable X with probability density function f(x), write code or describe an algorithm to construct its cumulative distribution function F(x) = P(X <= x). Handle both cases where the PDF is given in closed form and where it is available only as sampled (x, f(x)) points. Explain how you would deal with finite or infinite support, piecewise PDFs, numerical integration, normalization, and how to guarantee that the returned CDF is non-decreasing and approaches 0 and 1 at the boundaries.

Convert a PDF to a CDF

You are given sampled values of a continuous probability density function as a list of points (x, f(x)). These points may come from breakpoints of a piecewise closed-form PDF or from numeric samples of a PDF whose true support may be finite or truncated from an infinite range.

Construct the cumulative distribution function F(q) = P(X <= q) and return its value for each query point.

Use the following rules:

1. Sort the points by x.
2. If the same x appears multiple times, keep the largest density value at that x.
3. Negative density values are numerical noise and must be treated as 0.
4. Between consecutive sample points, assume the PDF is linearly interpolated.
5. Integrate the PDF under these line segments exactly (equivalently, use trapezoid areas).
6. If the total area is not 1, normalize the cumulative areas by the total area.
7. For any query q <= min_x, return 0.0. For any query q >= max_x, return 1.0.
8. The returned CDF values must be rounded to 6 decimal places.

This makes the method exact for piecewise-linear PDFs and a numerical approximation for arbitrary sampled PDFs, while ensuring the returned CDF is non-decreasing and reaches 0 and 1 at the boundaries.

Constraints

• 1 <= len(points), len(queries) <= 200000
• points[i] = (x_i, y_i) where x_i and y_i are real numbers
• After clipping negative densities to 0 and merging duplicate x-values, there is at least one positive-width interval and the total integrated area is positive
• |x_i|, |y_i|, |queries[i]| <= 1e9

Examples

Example 1

Input: ([(0, 0), (1, 1), (2, 0)], [-1, 0, 1, 2, 3])
Output: [0.0, 0.0, 0.5, 1.0, 1.0]

Explanation: This is a symmetric triangular PDF on [0, 2] with total area 1. The CDF at x = 1 is 0.5.

Example 2

Input: ([(0, 1), (2, 1)], [0, 1, 2])
Output: [0.0, 0.5, 1.0]

Explanation: The PDF is constant on [0, 2], so after normalization the midpoint has cumulative probability 0.5.

Hints

1. After sorting by x, think of each neighboring pair of points as one trapezoid under a piecewise-linear PDF.
2. Precompute prefix areas, then use binary search to locate the interval containing each query.